1231. Divide Chocolate
Problem Description
In this problem, you are given an array sweetness
, where each element represents the sweetness level of a chunk of chocolate. You also have k
friends with whom you want to share the chocolate. You plan to make k
cuts to the chocolate bar, resulting in k + 1
pieces, each composed of consecutive chunks.
Your goal is to be generous with your friends and, therefore, you will choose the least sweet piece for yourself. However, you want to optimize this so that this least sweet piece is as sweet as possible. The task is to find the maximum sweetness you can get for your piece after making the k
cuts in the best possible way.
Intuition
The solution leverages a binary search algorithm to find the optimal maximum sweetness you can achieve for your chocolate piece. The key insight is to realize that there is a range of possible sweetness levels for your piece – at the minimum, it could be the sweetness of the least sweet chunk, and at the maximum, it could be the total sweetness of the entire chocolate bar divided by k + 1
.
The binary search approach gradually narrows down this range by guessing a potential maximum sweetness (mid
), then checking if it's possible to cut the bar into k + 1
pieces where each piece has at least this level of sweetness. The check
function is used to determine whether the current guess can be achieved by summing up the chunks' sweetness until it meets or exceeds the guessed level before making a cut. If the function can make more than k
such valid cuts, the guess is feasible, and it means you might be able to increase the sweetness level for your piece, so you search in the higher half. Otherwise, the guess is too high, and you search in the lower half.
By repeatedly applying the binary search, you narrow down to the optimal l
value, which represents the maximum sweetness you can achieve for your chocolate piece.
Learn more about Binary Search patterns.
Solution Approach
The solution uses binary search to efficiently find the optimal cut points within the chocolate bar to maximize the sweetness of the piece you will eat. Below is the step-by-step explanation of the implementation:
-
First, we establish the search boundaries for binary search. The
l
(left boundary) is initialized to0
, assuming we cannot have a negative sweetness value, andr
(right boundary) is initialized to the sum of all chunks' sweetness since this is the maximum sweetness we could potentially achieve if we didn't have to share with anyone. -
We create a helper function
check(x)
with the parameterx
representing the current guess for the maximum sweetness of the piece. It will returnTrue
if it is possible to cut the bar into more thank
pieces where each piece has at leastx
sweetness. The function does this by iterating over the sweetness values, accumulating them until they reach or exceedx
, then making a virtual cut and proceeding with the rest of the chunks. -
Inside the while loop, which continues until
l < r
, we calculate the midpointmid
with(l + r + 1) >> 1
. The operation>> 1
is equivalent to integer division by 2, so this finds the middle value betweenl
andr
. The+1
is important as it helps to avoid an infinite loop whenl
andr
are close together. -
The
if
condition inside the while loop uses thecheck(mid)
function to decide which half of the current range to discard:-
If
check(mid)
returnsTrue
, it means it's possible to cut the chocolate into pieces where each has at leastmid
sweetness. Therefore, we should try to find a potentially higher minimum sweetness, and we updatel
tomid
. -
If
check(mid)
returnsFalse
, it meansmid
is too high of a value for the minimum piece sweetness that we can assure for ourselves after doing the cuts. Thus, we updater
tomid - 1
.
-
-
The loop will exit when
l
equalsr
, which means we found the maximum sweetness that can still satisfy the conditions. The solution returnsl
, which is the optimal maximum sweetness we can achieve for our piece of chocolate.
This algorithm ensures we arrive at the ideal maximum minimum sweetness while making sure that the rest of the chocolate pieces are fair enough to be distributed to the k
friends.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through an example to illustrate the solution approach. Suppose the sweetness
array is [1, 2, 3, 4, 5, 6, 7, 8, 9]
, and you have k=2
friends.
Our goal is to find the maximum sweetness for the least sweet piece we can have after k
cuts.
-
We initialize
l=0
andr=45
because 45 is the total sweetness (sum of all chunks) and thek+1
pieces implies that the maximum single piece's sweetness can't be more than45/3=15
. -
We create a helper function,
check(x)
, which will go through the sweetness array, summing the values until it reaches or exceeds the current guess x, and then count a cut. -
Enter the binary search while-loop:
-
First iteration:
l=0
,r=45
, somid=(0+45+1) >> 1 = 23
.- Check if it's possible to cut the bar so that each piece is at least
23
sweetness: No, because the highest sum we can get before the total sum exceeds 23 is1+2+3+4+5+6=21
, then7+8+9=24
, which only makes 1 cut. So, updater
tomid - 1
, which is22
.
- Check if it's possible to cut the bar so that each piece is at least
-
Second iteration:
l=0
,r=22
, somid=(0+22+1) >> 1 = 11
.- Check if it's possible with
11
: Yes, one piece can be1+2+3+4=10
(which is just under 11), the next can be5+6=11
, and the last piece will be7+8+9=24
(far exceeding 11, but it's the last piece, so it's okay). We managed more thank
cuts here, so updatel
tomid
, which is11
.
- Check if it's possible with
-
Third iteration:
l=11
,r=22
, somid=(11+22+1) >> 1 = 17
.- With
17
, we can't reach the minimum sweetness before we've hit the end of the array (again, we get chunks like1+2+3+4+5=15
and then6+7+8+9=30
), resulting in only 1 cut, so updater
tomid - 1
, which is16
.
- With
-
Fourth iteration:
l=11
,r=16
, somid=(11+16+1) >> 1 = 14
.- Attempt with
14
: We can have the pieces1+2+3+4+5=15
and6+7=13
(below 14, so we keep adding) then8+9=17
, we're just making 2 cuts. Since we succeeded in makingk
cuts before the sum fell short of14
, we can continue searching between14
to16
.
- Attempt with
-
The process will continue, narrowing down the range until
l
equalsr
.
-
-
By the end of the last iteration, when
l
equalsr
, we have found the right cut-off (mid
) where we can still have more thank
cuts with each piece being at least as sweet as our final value ofl
. -
The final value of
l
will be our answer. In this example, the maximum sweetness for the least sweet piece you can have would be11
after iterating this process to the point wherel
andr
converge.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
5 # Helper function to check if the minimum sweetness value 'min_sweetness'
6 # allows us to divide the chocolate into more than k+1 pieces
7 def can_divide(min_sweetness: int) -> bool:
8 total = 0
9 pieces = 0
10 # Go through each piece of the chocolate
11 for piece_sweetness in sweetness:
12 total += piece_sweetness
13 # If the total sweetness is at least 'min_sweetness',
14 # we can form a new piece
15 if total >= min_sweetness:
16 total = 0
17 pieces += 1
18 # The +1 is because we need to divide the chocolate into k+1 pieces
19 return pieces > k
20
21 # Initialize binary search bounds
22 # 'left' is the minimum possible sweetness, 'right' is the maximum possible sweetness
23 left, right = 1, sum(sweetness)
24 # Perform binary search to find the maximum minimum sweetness
25 while left < right:
26 # Calculate the middle point of the current search range
27 mid = (left + right + 1) // 2
28 # If we can divide the chocolate with 'mid' sweetness,
29 # we try to find a higher minimum sweetness value
30 if can_divide(mid):
31 left = mid
32 else:
33 # Otherwise, if we cannot, we look for a smaller minimum sweetness value
34 right = mid - 1
35 # Return the maximum minimum sweetness value we found
36 return left
37
1class Solution {
2 public int maximizeSweetness(int[] sweetness, int k) {
3 // Initialize the range of sweetness we will search within.
4 int left = 1; // The minimum sweetness can't be less than 1 (assuming sweetness array is positive).
5 int right = 0; // The maximum sweetness possible.
6
7 // Calculate the total sweetness in the array, which is the upper limit for binary search.
8 for (int sweet : sweetness) {
9 right += sweet;
10 }
11
12 // Perform a binary search to find the maximum sweetness that can be achieved.
13 while (left < right) {
14 // Use the mid point of the current range to test the sweetness level.
15 int mid = (left + right + 1) >>> 1;
16
17 // Check if it's possible to have more than k pieces with at least 'mid' sweetness.
18 if (canSplit(sweetness, mid, k)) {
19 left = mid; // If possible, search towards the higher end of the range.
20 } else {
21 right = mid - 1; // Otherwise, search towards the lower end of the range.
22 }
23 }
24
25 // Return the maximum sweetness level found.
26 return left;
27 }
28
29 private boolean canSplit(int[] sweetnessArray, int minimumSweetness, int k) {
30 int currentSum = 0; // Current piece sweetness sum.
31 int pieces = 0; // Number of pieces formed.
32
33 // Sum up sweetness pieces and count how many are >= minimumSweetness.
34 for (int sweet : sweetnessArray) {
35 currentSum += sweet;
36 // When we reach the minimum sweetness for the current piece, increment piece count.
37 if (currentSum >= minimumSweetness) {
38 pieces++;
39 currentSum = 0; // Reset the sum for the next piece.
40 }
41 }
42
43 // Check if we can have one more piece for the divider (k pieces means k+1 friends).
44 // Return true if pieces count is greater than k.
45 return pieces >= k + 1;
46 }
47}
48
1#include <vector>
2#include <numeric>
3
4class Solution {
5public:
6 // Function to maximize the minimum sweetness of the pieces divided
7 // Parameters:
8 // sweetness: vector of integers where each integer represents the sweetness of a piece
9 // k: number of friends to share the sweetness with (pieces to divide into k+1)
10 int maximizeSweetness(vector<int>& sweetness, int k) {
11 int left = 1; // minimum possible sweetness
12 int right = accumulate(sweetness.begin(), sweetness.end(), 0); // maximum possible sweetness
13
14 // Helper lambda to check if a given minimum sweetness value is achievable
15 auto canAchieveSweetness = [&](int minSweetness) {
16 int currentSum = 0, cuts = 0;
17 for (int pieceSweetness : sweetness) {
18 currentSum += pieceSweetness;
19 if (currentSum >= minSweetness) {
20 currentSum = 0;
21 ++cuts; // Increase count of number of cuts/pieces
22 }
23 }
24 return cuts >= k + 1; // Check if we can make k+1 pieces
25 };
26
27 // Binary search to find the maximum of the minimum sweetness that we can achieve
28 while (left < right) {
29 int mid = left + (right - left + 1) / 2; // Midpoint and to avoid integer overflow
30
31 // If the current mid can achieve the minimum sweetness, search towards the higher end
32 if (canAchieveSweetness(mid)) {
33 left = mid;
34 } else {
35 right = mid - 1; // Otherwise, search towards the lower end
36 }
37 }
38
39 // left will be the maximum of the minimum sweetness we can achieve
40 return left;
41 }
42};
43
1function maximizeSweetness(sweetness: number[], k: number): number {
2 let left = 0; // Initialize the lower bound of binary search
3 let right = sweetness.reduce((a, b) => a + b); // Initialize the upper bound as the sum of sweetness
4
5 // Define a helper function to check if it's possible to split the sweetness array
6 // into more than k parts where each part has a minimum total sweetness of x
7 const canSplit = (minimumSweetness: number): boolean => {
8 let currentSweetness = 0;
9 let partsCount = 0;
10 for (const value of sweetness) {
11 currentSweetness += value; // Add the sweetness value to the current sum
12 // If the current sum reaches the minimum sweetness threshold, we start a new part
13 if (currentSweetness >= minimumSweetness) {
14 currentSweetness = 0; // Reset the current sweetness for the next part
15 partsCount++; // Increment the count of parts
16 }
17 }
18 // Check if we can have more than k parts with the specified minimum sweetness
19 return partsCount > k;
20 };
21
22 // Use binary search to find the maximum minimum sweetness
23 while (left < right) {
24 const mid = (left + right + 1) >> 1; // Equivalent to Math.floor((left + right + 1) / 2)
25 // If it's possible to split into more than k parts with mid as minimum sweetness,
26 // it means we can try a higher minimum. So we update left to mid.
27 if (canSplit(mid)) {
28 left = mid;
29 } else {
30 // Otherwise, we need to look for a smaller minimum sweetness
31 right = mid - 1;
32 }
33 }
34 // After binary search, left will be the maximum minimum sweetness we can achieve
35 return left;
36}
37
Time and Space Complexity
The given Python code aims to maximize the sweetness of the piece a person can get after dividing the chocolate sweetness
array into k + 1
pieces. It uses a binary search approach to find the solution.
Time Complexity
The binary search runs while l < r
, which typically gives us a O(log n)
complexity, where n
is the range of values to be searched—in this case, the total sum of the sweetness
array (sum(sweetness)
).
Within each iteration of the binary search, the check
function is called, which itself runs through the entire array once. Therefore, this part has a time complexity of O(m)
, where m
is the length of the sweetness
array.
Combining these two parts together, we get a total time complexity of O(m * log n)
for the entire algorithm, taking into account the binary search and the linear scan in the check
function for each mid value.
Space Complexity
The space complexity is O(1)
. No additional space is allocated that grows with the size of the input, as the variables l
, r
, mid
, s
, cnt
, and x
only use a constant amount of space.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!