Divide Chocolate

Medium
830.

Divide Chocolate

Divide Chocolate is a medium coding problem on arrays, greedy and binary search, asked in Amazon, Google and Zoho interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} sweetness
 * @param {number} k
 * @return {number}
 */
var maximizeSweetness = function(sweetness, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Divide Chocolate

  1. Hint 1

    You keep the minimum piece, so this is a maximise-the-minimum problem — binary search the answer.

  2. Hint 2

    For a candidate minimum m, greedily cut as soon as the running sum reaches m.

  3. Hint 3

    Feasible when that produces at least k + 1 pieces.

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

Java

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