Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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:

1
2
3
4
5

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

  • 1 <= sweetness.length <= 10^4
  • 1 <= sweetness[i] <= 10^5
  • 1 <= K <= sweetness.length - 1

Solution

Method 1 – Binary Search on Answer

Intuition

We want to maximize the minimum sweetness among all pieces after making K cuts. If we try a candidate minimum sweetness, we can check if it’s possible to split the chocolate into at least K+1 pieces, each with at least that much sweetness. If yes, we can try a higher value; if not, we try lower. This is a classic binary search on the answer.

Approach

  1. Set low to 1 and high to the total sweetness divided by (K+1).
  2. Use binary search to find the largest minimum sweetness possible:
    • For each mid value, check if you can split the array into at least K+1 pieces, each with at least mid sweetness.
    • If possible, move low up; otherwise, move high down.
  3. The answer is the highest minimum sweetness found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int maximizeSweetness(vector<int>& s, int k) {
        int l = 1, r = accumulate(s.begin(), s.end(), 0) / (k+1), ans = 0;
        while (l <= r) {
            int m = l + (r-l)/2, cnt = 0, sum = 0;
            for (int x : s) {
                sum += x;
                if (sum >= m) {
                    cnt++;
                    sum = 0;
                }
            }
            if (cnt >= k+1) ans = m, l = m+1;
            else r = m-1;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func maximizeSweetness(s []int, k int) int {
    l, r := 1, 0
    for _, v := range s {
        r += v
    }
    r /= (k+1)
    ans := 0
    for l <= r {
        m := l + (r-l)/2
        cnt, sum := 0, 0
        for _, x := range s {
            sum += x
            if sum >= m {
                cnt++
                sum = 0
            }
        }
        if cnt >= k+1 {
            ans = m
            l = m+1
        } else {
            r = m-1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int maximizeSweetness(int[] s, int k) {
        int l = 1, r = 0, ans = 0;
        for (int v : s) r += v;
        r /= (k+1);
        while (l <= r) {
            int m = l + (r-l)/2, cnt = 0, sum = 0;
            for (int x : s) {
                sum += x;
                if (sum >= m) {
                    cnt++;
                    sum = 0;
                }
            }
            if (cnt >= k+1) {
                ans = m;
                l = m+1;
            } else {
                r = m-1;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    fun maximizeSweetness(s: IntArray, k: Int): Int {
        var l = 1
        var r = s.sum() / (k+1)
        var ans = 0
        while (l <= r) {
            val m = l + (r-l)/2
            var cnt = 0
            var sum = 0
            for (x in s) {
                sum += x
                if (sum >= m) {
                    cnt++
                    sum = 0
                }
            }
            if (cnt >= k+1) {
                ans = m
                l = m+1
            } else {
                r = m-1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def maximizeSweetness(self, s: list[int], k: int) -> int:
        l, r = 1, sum(s) // (k+1)
        ans = 0
        while l <= r:
            m = (l + r) // 2
            cnt, sm = 0, 0
            for x in s:
                sm += x
                if sm >= m:
                    cnt += 1
                    sm = 0
            if cnt >= k+1:
                ans = m
                l = m+1
            else:
                r = m-1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn maximize_sweetness(s: Vec<i32>, k: i32) -> i32 {
        let (mut l, mut r) = (1, s.iter().sum::<i32>() / (k+1));
        let mut ans = 0;
        while l <= r {
            let m = l + (r-l)/2;
            let mut cnt = 0;
            let mut sum = 0;
            for &x in &s {
                sum += x;
                if sum >= m {
                    cnt += 1;
                    sum = 0;
                }
            }
            if cnt >= k+1 {
                ans = m;
                l = m+1;
            } else {
                r = m-1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    maximizeSweetness(s: number[], k: number): number {
        let l = 1, r = Math.floor(s.reduce((a, b) => a + b, 0) / (k+1)), ans = 0;
        while (l <= r) {
            let m = Math.floor((l + r) / 2), cnt = 0, sum = 0;
            for (let x of s) {
                sum += x;
                if (sum >= m) {
                    cnt++;
                    sum = 0;
                }
            }
            if (cnt >= k+1) {
                ans = m;
                l = m+1;
            } else {
                r = m-1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log S), where n is the length of sweetness and S is the sum of all sweetness. Each binary search step checks the array in O(n).
  • 🧺 Space complexity: O(1), only constant extra space is used for variables.