Coding

Divide Chocolate

Asked at

Sprinklr

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness. You want to share the chocolate with your k friends so you start cutting the chocolate bar into k + 1 pieces using k cuts, each piece consists of some consecutive chunks. Being generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends. Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5 Output: 6 Explanation: You can divide the chocolate to [1,2,3], [4,5], [6], [7], [8], [9]

Input: sweetness = [1,2,2,1,2,2,1,2,2], k = 2 Output: 5 Explanation: You can divide the chocolate to [1,2,2], [1,2,2], [1,2,2]

Input: sweetness = [1,2,3,4,5,6], k = 2

0 <= k < sweetness.length <= 104
1 <= sweetness[i] <= 105

cpp

class Solution {
public:
    int maximizeSweetness(vector<int>& sweetness, int k) {
        // User code goes here
    }
};

java

class Solution {
    public int maximizeSweetness(int[] sweetness, int k) {
        // User code goes here
    }
}

python

class Solution:
    def maximizeSweetness(self, sweetness, k):
        # User code goes here

javascript

class Solution {
    maximizeSweetness(sweetness, k) {
        // User code goes here
    }
}

csharp

public class Solution {
    public int MaximizeSweetness(int[] sweetness, int k) {

    }
}

func maximizeSweetness(sweetness []int, k int) int {

}

Stuck? Show a way to structure it+

01Binary-search a proposed minimum sweetness.
02Greedily cut whenever the running sum reaches that proposal.
03Count pieces; feasibility requires at least k+1 pieces.
04Keep the greatest feasible proposal.

Reference answer

If every final piece must have sweetness at least x, scan left to right, accumulate chunks, and cut as soon as the sum reaches x. This greedy strategy maximizes the number of qualifying pieces because delaying a valid cut only consumes sweetness needed by later pieces. The predicate is feasible when at least k+1 pieces can be formed, since there are k friends plus you. It is monotonic, so binary-search x from 1 to sum(sweetness) / (k+1). Time is O(n log S), where S is the sum, with O(1) extra space. Do not accidentally require exactly k cuts in the greedy check; extra potential pieces are fine.

Then expect these follow-ups

How would you minimize the largest partition sum instead?
Tests: dual binary-search pattern
Why is cutting as soon as possible safe?
Tests: greedy proof

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question