1231. Divide Chocolate 🔒

SourceBiweekly Contest 11 Q4DifficultyHardRating2029

Description

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.

Example 1:

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]

Example 2:

Input: sweetness = [5,6,7,8,9,1,2,3,4], k = 8
Output: 1
Explanation: There is only one way to cut the bar into 9 pieces.

Example 3:

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]

Constraints:

0 <= k < sweetness.length <= 10⁴
1 <= sweetness[i] <= 10⁵

Solutions

Solution 1: Binary Search + Greedy

Thinking

We split the bar into \(k+1\) pieces and maximize the minimum sweetness of our piece. \(n \le 10^4\) forbids enumerating cuts. If a minimum \(x\) is feasible, every smaller threshold is too, so the answer is monotone.

The check accumulates from the left and cuts whenever the running sum reaches \(x\); more than \(k\) pieces (us plus \(k\) friends) means \(x\) works. We binary-search the largest feasible \(x\) on \([0,\sum sweetness]\). Cutting as soon as a piece fills can only leave more remainder for later pieces.

We notice that if we can eat a piece of chocolate with sweetness \(x\), then we can also eat all chocolates with sweetness less than or equal to \(x\). This shows monotonicity, therefore, we can use binary search to find the maximum \(x\) that satisfies the condition.

We define the left boundary of the binary search as \(l=0\), and the right boundary as \(r=\sum_{i=0}^{n-1} sweetness[i]\). Each time, we take the middle value \(mid\) of \(l\) and \(r\), and then determine whether we can eat a piece of chocolate with sweetness \(mid\). If we can, then we try to eat a piece of chocolate with greater sweetness, i.e., let \(l=mid\); otherwise, we try to eat a piece of chocolate with smaller sweetness, i.e., let \(r=mid-1\). After the binary search ends, we return \(l\).

The key to the problem is how to determine whether we can eat a piece of chocolate with sweetness \(x\). We can use a greedy approach, traverse the array from left to right, accumulate the current sweetness each time, when the accumulated sweetness is greater than or equal to \(x\), the chocolate count \(cnt\) is increased by \(1\), and the accumulated sweetness is reset to zero. Finally, check whether \(cnt\) is greater than \(k\).

The time complexity is \(O(n \times \log \sum_{i=0}^{n-1} sweetness[i])\), and the space complexity is \(O(1)\). Where \(n\) is the length of the array.

Python3JavaC++GoTypeScript

class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        def check(x: int) -> bool:
            s = cnt = 0
            for v in sweetness:
                s += v
                if s >= x:
                    s = 0
                    cnt += 1
            return cnt > k

        l, r = 0, sum(sweetness)
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

class Solution {
    public int maximizeSweetness(int[] sweetness, int k) {
        int l = 0, r = 0;
        for (int v : sweetness) {
            r += v;
        }
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(sweetness, mid, k)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    private boolean check(int[] nums, int x, int k) {
        int s = 0, cnt = 0;
        for (int v : nums) {
            s += v;
            if (s >= x) {
                s = 0;
                ++cnt;
            }
        }
        return cnt > k;
    }
}

class Solution {
public:
    int maximizeSweetness(vector<int>& sweetness, int k) {
        int l = 0, r = accumulate(sweetness.begin(), sweetness.end(), 0);
        auto check = [&](int x) {
            int s = 0, cnt = 0;
            for (int v : sweetness) {
                s += v;
                if (s >= x) {
                    s = 0;
                    ++cnt;
                }
            }
            return cnt > k;
        };
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
};

func maximizeSweetness(sweetness []int, k int) int {
    l, r := 0, 0
    for _, v := range sweetness {
        r += v
    }
    check := func(x int) bool {
        s, cnt := 0, 0
        for _, v := range sweetness {
            s += v
            if s >= x {
                s = 0
                cnt++
            }
        }
        return cnt > k
    }
    for l < r {
        mid := (l + r + 1) >> 1
        if check(mid) {
            l = mid
        } else {
            r = mid - 1
        }
    }
    return l
}

function maximizeSweetness(sweetness: number[], k: number): number {
    let l = 0;
    let r = sweetness.reduce((a, b) => a + b);
    const check = (x: number): boolean => {
        let s = 0;
        let cnt = 0;
        for (const v of sweetness) {
            s += v;
            if (s >= x) {
                s = 0;
                ++cnt;
            }
        }
        return cnt > k;
    };
    while (l < r) {
        const mid = (l + r + 1) >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

1231. Divide Chocolate 🔒

Description

Solutions

Solution 1: Binary Search + Greedy

Comments