Divide Chocolate

hard binary search greedy array

Problem

You have a chocolate bar of consecutive chunks given by sweetness[]. You will make k cuts to split it into k + 1 contiguous pieces. You keep the piece with the minimum total sweetness and give the rest away. Return the maximum total sweetness your piece can have over all ways of cutting.

Inputsweetness = [1, 2, 3, 4, 5, 6, 7, 8, 9], k = 5

Output6

Cut into [1,2,3], [4,5], [6], [7], [8], [9]. The minimum piece sums to 6, which is the best achievable.

sweetness (comma-separated)

k (cuts)

def maximizeSweetness(sweetness, k):
    def pieces(limit):
        count, cur = 0, 0
        for s in sweetness:
            cur += s
            if cur >= limit:
                count += 1
                cur = 0
        return count

    lo, hi = min(sweetness), sum(sweetness) // (k + 1)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if pieces(mid) >= k + 1:
            lo = mid
        else:
            hi = mid - 1
    return lo

function maximizeSweetness(sweetness, k) {
  const pieces = (limit) => {
    let count = 0, cur = 0;
    for (const s of sweetness) {
      cur += s;
      if (cur >= limit) { count++; cur = 0; }
    }
    return count;
  };

  let lo = Math.min(...sweetness);
  let hi = Math.floor(sweetness.reduce((a, b) => a + b, 0) / (k + 1));
  while (lo < hi) {
    const mid = Math.floor((lo + hi + 1) / 2);
    if (pieces(mid) >= k + 1) lo = mid;
    else hi = mid - 1;
  }
  return lo;
}

class Solution {
    public int maximizeSweetness(int[] sweetness, int k) {
        int lo = Integer.MAX_VALUE, total = 0;
        for (int s : sweetness) { lo = Math.min(lo, s); total += s; }
        int hi = total / (k + 1);
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (pieces(sweetness, mid) >= k + 1) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }

    private int pieces(int[] sweetness, int limit) {
        int count = 0, cur = 0;
        for (int s : sweetness) {
            cur += s;
            if (cur >= limit) { count++; cur = 0; }
        }
        return count;
    }
}

int maximizeSweetness(vector<int>& sweetness, int k) {
    auto pieces = [&](int limit) {
        int count = 0, cur = 0;
        for (int s : sweetness) {
            cur += s;
            if (cur >= limit) { count++; cur = 0; }
        }
        return count;
    };

    int lo = *min_element(sweetness.begin(), sweetness.end());
    int total = accumulate(sweetness.begin(), sweetness.end(), 0);
    int hi = total / (k + 1);
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (pieces(mid) >= k + 1) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

Explanation

We keep the piece with the smallest sweetness, and we want to make that smallest piece as large as possible. This "maximize the minimum" goal is the signal for binary search on the answer.

The candidate answer is a target sweetness limit for the minimum piece. It can range from min(sweetness) (one chunk could be the smallest piece) up to sum(sweetness) / (k+1) (you can't beat the average split).

The helper pieces(limit) greedily counts how many pieces we can carve where each has sum at least limit: walk the chunks, keep a running cur, and whenever cur >= limit finish a piece and reset. If it produces >= k + 1 pieces, that limit is achievable.

Since larger limits are harder, we search for the biggest feasible one. When pieces(mid) >= k + 1 we raise the floor with lo = mid; otherwise we lower the ceiling with hi = mid - 1. The +1 in mid = (lo + hi + 1) / 2 avoids an infinite loop when hunting the upper bound.

Example: sweetness = [1..9], k = 5 (so 6 pieces). The best minimum is 6, achieved by [1,2,3] [4,5] [6] [7] [8] [9]. The search runs in O(n log S).

Time: O(n log S) Space: O(1)