Get started

Divide Chocolate — Medium Problem & Solution

A chocolate bar is a row of chunks with the given sweetness values.

  • 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 <= 10000
  • 1 <= sweetness[i] <= 100000

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

  1. Search m over [min(sweetness), total / (k + 1)].
  2. can(m): accumulate chunks, closing a piece each time the running sum reaches m; feasible when at least k + 1 pieces close.
  3. 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

  • k cuts make k + 1 pieces — 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue