Divide Chocolate — Solution in Python, Java & C++
Divide Chocolate solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and greedy.
Divide Chocolate is a medium coding problem on arrays, greedy and binary search, asked in Amazon, Google and Zoho interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy, Binary Search
- Asked at: Amazon, Google, Zoho
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A chocolate bar is a row of chunks with the given sweetness values. You make k cuts between chunks, producing k + 1 consecutive pieces, and give one piece to each of your k friends — keeping the least sweet piece for yourself.
Return the maximum total sweetness your piece can have.
Example 1
Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6
Explanation: Cut into [1,2,3], [4,5], [6], [7], [8] and [9].
Example 2
Input: sweetness = [5,6,7,8,9,1,2,3,4], k = 8
Output: 1
Explanation: Every chunk becomes its own piece.
Example 3
Input: sweetness = [1,2,2,1,2,2,1,2,2], k = 2
Output: 5
Constraints
0 <= k < sweetness.length <= 100001 <= sweetness[i] <= 100000
Hints for Divide Chocolate
Hint 1
You keep the minimum piece, so this is a maximise-the-minimum problem — binary search the answer.
Hint 2
For a candidate minimum
m, greedily cut as soon as the running sum reachesm.Hint 3
Feasible when that produces at least
k + 1pieces.
How to solve Divide Chocolate
Binary search the value of your piece. For a candidate minimum m, the greedy that closes a piece the moment its sum reaches m produces the most pieces of sweetness at least m, so it decides feasibility exactly.
Approach
- Search
mover[min(sweetness), total / (k + 1)]. can(m): accumulate chunks, closing a piece each time the running sum reachesm; feasible when at leastk + 1pieces close.- Take the largest feasible
m, using the upper-biased midpoint.
Why it works
Closing a piece as soon as it qualifies is optimal: carrying extra sweetness forward can only make later pieces harder to fill, never easier. Raising m makes each piece need more chunks, so the piece count is non-increasing — the monotonicity binary search needs. The upper bound total / (k + 1) holds because the pieces partition the bar.
Complexity
- Time —
O(n log S) where S is the total sweetness - Space —
O(1)
Pitfalls
kcuts makek + 1pieces — the off-by-one here is the usual mistake.- The upper-biased midpoint is required for a maximise search, or the loop never terminates.
- Leftover chunks after the last closed piece simply join it, which is why only the piece count is checked.
Reference solution
Python
from typing import List
def maximizeSweetness(sweetness: List[int], k: int) -> int:
lo, hi = min(sweetness), sum(sweetness) // (k + 1)
def can(m: int) -> bool:
pieces, cur = 0, 0
for s in sweetness:
cur += s
if cur >= m:
pieces += 1
cur = 0
return pieces >= k + 1
while lo < hi:
mid = (lo + hi + 1) // 2
if can(mid):
lo = mid
else:
hi = mid - 1
return loJava
private static boolean canSweeten(int[] sweetness, int k, int m) {
int pieces = 0, cur = 0;
for (int s : sweetness) {
cur += s;
if (cur >= m) {
pieces++;
cur = 0;
}
}
return pieces >= k + 1;
}
public static int maximizeSweetness(int[] sweetness, int k) {
int lo = sweetness[0];
long total = 0;
for (int s : sweetness) {
lo = Math.min(lo, s);
total += s;
}
int hi = (int) (total / (k + 1));
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (canSweeten(sweetness, k, mid)) lo = mid; else hi = mid - 1;
}
return lo;
}C++
static bool canSweeten(vector<int>& sweetness, int k, int m) {
int pieces = 0, cur = 0;
for (int s : sweetness) {
cur += s;
if (cur >= m) {
pieces++;
cur = 0;
}
}
return pieces >= k + 1;
}
int maximizeSweetness(vector<int>& sweetness, int k) {
int lo = sweetness[0];
long long total = 0;
for (int s : sweetness) {
lo = min(lo, s);
total += s;
}
int hi = (int) (total / (k + 1));
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (canSweeten(sweetness, k, mid)) lo = mid; else hi = mid - 1;
}
return lo;
}JavaScript
var maximizeSweetness = function(sweetness, k) {
var lo = sweetness[0], total = 0, i;
for (i = 0; i < sweetness.length; i++) {
if (sweetness[i] < lo) lo = sweetness[i];
total += sweetness[i];
}
var hi = Math.floor(total / (k + 1));
var can = function(m) {
var pieces = 0, cur = 0;
for (var j = 0; j < sweetness.length; j++) {
cur += sweetness[j];
if (cur >= m) { pieces++; cur = 0; }
}
return pieces >= k + 1;
};
while (lo < hi) {
var mid = Math.ceil((lo + hi) / 2);
if (can(mid)) lo = mid; else hi = mid - 1;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms