Good day! Hope your workday has started on the right note. Currently in the USA we are observing the Daylight saving time which this year ends on Sunday, November 7, 2021. Today is Thursday October 14, 2021 so we have a little over one month for the time to get back to normal.
I see the positive sides of daylight savings time during summer. In my opinion, in the USA, daylight savings should start on Memorial Day and end on Labor Day. The reason for this is that schools and universities tend to be off during such period.
For college students it should not make much of a difference, but for K-12 students it does. Most children use public school buses to commute to school. Depending on the grade they attend, they may be picked up in the morning around 07:00 AM. I am always up before 06:00 AM. I am a morning person. After fixing breakfast I wake up my wife so we can have the first meal of the day together.
After we are done with breakfast, she helps me with the dishes. After rinsing the dishes and putting them in the dishwasher I shower, get dressed, and head down to my office to work on my first 2-hour block of the day. This includes weekends in which I work one or at most two blocks. On regular workdays I tend to do four to five blocks a day.
For the past week or two, when I head down to my office, the day is very dark, to the point that I have to turn on lights. It happens that when I am heading down is about 07:00 AM and I see kids that are already riding public school busses. They had to walk from home to the bus stop while it is quite dark. I thought that children were first in our society. It seems I am wrong. Go figure!
In the month that we have to wait before daylight savings ends, it will be dark close to 08:00 AM. So why is this happening? Well, the thought is that if the school day ends with some light, parents will be more prone to head out and grab a bite which is good for business. I guess children do not have much homework in these days. Things have changed since I attended K-12.
Yesterday I tacked the LeetCode 1231 Divide Chocolate problem which happens to be rated Hard. Not only that, but understanding what we are supposed to do is also hard.
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`. Constraints: o 0 <= k < sweetness.length <= 104 o 1 <= sweetness[i] <= 105 Hints: o After dividing the array into K+1 sub-arrays, you will pick the sub-array with the minimum sum. o Divide the sub-array into K+1 sub-arrays such that the minimum sub-array sum is as maximum as possible. o Use `binary search` with `greedy check`.
I like the part when one is `generous` by eating the piece with `minimum` sweetness. That implies less sugar. I would have thought that one would consume the one with `most` sugar and give away the pieces with `less` sweetness.
I checked the hints and found them helpful, specially the last one.
We will attempt to solve the problem using the Java programming language and the VSCode IDE on a Windows computer. Because of this, we will also need to write a simple test scaffold to read the input, populate variables, call the function of interest, and display the result. Please note that THIS IS NOT PART OF THE SOLUTION!
public int maximizeSweetness(int[] sweetness, int k) {
}
The signature for the function of interest calls for the array of sweetness and the number of pieces we need to cut the chocolate bar. Please take a few moments to understand what we need to do. If we have `k` friends we need to cut the chocolate bar into `k + 1` pieces so we need to perform `k` cuts.
Given the fact that we will use a modified binary search, I decided to generate the code for a standard binary search. That code IS NOT PART OF THE SOLUTION! I could just have pointed to other posts in this blog, but I wanted to refresh the algorithm. In production, you should avoid when possible writing code for such a common algorithm because chances are that you may introduce `bugs`. The best approach is not to reinvent the wheel and use a library.
1,2,3,4,5,6,7,8,9 5 main <<< sweetness: [1, 2, 3, 4, 5, 6, 7, 8, 9] main <<< k: 5 main <<< inStr ["" to skip]: maximizeSweetness <<< low: 1 high: 7 maximizeSweetness <<< mid: 4 maximizeSweetness <<< low: 4 high: 7 maximizeSweetness <<< mid: 6 maximizeSweetness <<< low: 6 high: 7 maximizeSweetness <<< mid: 7 main <<< output: 6 5,6,7,8,9,1,2,3,4 8 main <<< sweetness: [5, 6, 7, 8, 9, 1, 2, 3, 4] main <<< k: 8 main <<< inStr ["" to skip]: maximizeSweetness <<< low: 1 high: 5 maximizeSweetness <<< mid: 3 maximizeSweetness <<< low: 1 high: 2 maximizeSweetness <<< mid: 2 main <<< output: 1 1,2,2,1,2,2,1,2,2 2 main <<< sweetness: [1, 2, 2, 1, 2, 2, 1, 2, 2] main <<< k: 2 main <<< inStr ["" to skip]: maximizeSweetness <<< low: 1 high: 5 maximizeSweetness <<< mid: 3 maximizeSweetness <<< low: 3 high: 5 maximizeSweetness <<< mid: 4 maximizeSweetness <<< low: 4 high: 5 maximizeSweetness <<< mid: 5 main <<< output: 5 1,2,3,4,5 3 main <<< sweetness: [1, 2, 3, 4, 5] main <<< k: 3 main <<< inStr ["" to skip]: maximizeSweetness <<< low: 1 high: 3 maximizeSweetness <<< mid: 2 maximizeSweetness <<< low: 2 high: 3 maximizeSweetness <<< mid: 3 main <<< output: 3 22256,47646,19294,31272,75367 4 main <<< sweetness: [22256, 47646, 19294, 31272, 75367] main <<< k: 4 main <<< inStr ["" to skip]: maximizeSweetness <<< low: 1 high: 39167 maximizeSweetness <<< mid: 19584 maximizeSweetness <<< low: 1 high: 19583 maximizeSweetness <<< mid: 9792 maximizeSweetness <<< low: 9792 high: 19583 maximizeSweetness <<< mid: 14688 maximizeSweetness <<< low: 14688 high: 19583 maximizeSweetness <<< mid: 17136 maximizeSweetness <<< low: 17136 high: 19583 maximizeSweetness <<< mid: 18360 maximizeSweetness <<< low: 18360 high: 19583 maximizeSweetness <<< mid: 18972 maximizeSweetness <<< low: 18972 high: 19583 maximizeSweetness <<< mid: 19278 maximizeSweetness <<< low: 19278 high: 19583 maximizeSweetness <<< mid: 19431 maximizeSweetness <<< low: 19278 high: 19430 maximizeSweetness <<< mid: 19354 maximizeSweetness <<< low: 19278 high: 19353 maximizeSweetness <<< mid: 19316 maximizeSweetness <<< low: 19278 high: 19315 maximizeSweetness <<< mid: 19297 maximizeSweetness <<< low: 19278 high: 19296 maximizeSweetness <<< mid: 19287 maximizeSweetness <<< low: 19287 high: 19296 maximizeSweetness <<< mid: 19292 maximizeSweetness <<< low: 19292 high: 19296 maximizeSweetness <<< mid: 19294 maximizeSweetness <<< low: 19294 high: 19296 maximizeSweetness <<< mid: 19295 main <<< output: 19294
We are given two input lines. The first line contains an array of sweetness values and the second the number of friends.
Our test code seems to read in the proper values and populate the corresponding variables. This is illustrated by displaying them.
Our test program then requests us to enter a value which we would use to test our standard binary search code which IS NOT PART OF THE SOLUTION. In all the test cases we do not test the standard binary search, but the code is there and you can experiment with it.
We then seem to call the function of interest which displays some values. This is done to better follow and debug the function of interest. Note that it should include a modified binary search and a way to implement a Greedy algorithm.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read array of sweetness ****
int[] sweetness = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read k ****
int k = Integer.parseInt(br.readLine().trim());
// ???? ????
System.out.println("main <<< sweetness: " + Arrays.toString(sweetness));
System.out.println("main <<< k: " + k);
// ???? prompt for value to search in swetness[] and search (if needed) ????
System.out.print("main <<< inStr [\"\" to skip]: ");
String inStr = br.readLine().trim();
if (!inStr.equals("")) {
int s = Integer.parseInt(inStr);
System.out.println("main <<< s: " + s);
System.out.println("main <<< search: " + search(sweetness, s));
}
// **** close buffered reader ****
br.close();
// **** call function of interest and display result ****
System.out.println("main <<< output: " + maximizeSweetness(sweetness, k));
}
This is our test scaffold which IS NOT PART OF THE SOLUTION. We open a buffered reader and read in the values for the sweetness array and the number of friends.
We then prompt the user to enter an integer which we will attempt to find in the sweetness array. If the user enters a <Return> then the binary search is skipped.
We close the buffered reader, call the function of interest and display the returned value. Simple and to the point! I always like to use the KISS principle to get to a minimum viable product.
/**
* Binary search entry point.
* Returns the index in arr[] for target (if found).
* !!! NOT PART OF THE SOLUTION!!!
*/
static int search(int[] arr, int target) {
// **** sanity check(s) ****
if (arr.length == 1) {
if (arr[0] == target) return 0;
else return -1;
}
// **** start recursion ****
int ndex = search(arr, target, 0, arr.length - 1);
// **** return index of target in arr[] ****
return ndex;
}
This is the entry point for our implementation of a standard binary search which is NOT PART OF THE SOLUTION. We pass an array and the target value. We perform a sanity check, start the recursion process and when done, return the index of the array holding the target value. If not found, we return -1.
/**
* Binary search recursive call.
* !!! NOT PART OF THE SOLUTION!!!
*/
private static int search(int[] arr, int target, int left, int right) {
// **** base case ****
if (left > right) return -1;
// **** compute mid value ****
int mid = left + (right - left) / 2;
// **** check if target was found ****
if (arr[mid] == target) return mid;
// **** decide which way to go ****
if (target > arr[mid]) left = mid + 1; // go right
else right = mid - 1; // go left
// **** recursive call ****
return search(arr, target, left, right);
}
This is the recursive call for the binary search that is NOT PART OF THE SOLUTION.
We start with a base case that indicates that we are done with the search.
If we continue (not reached the base case), we compute the mid value in the array.
We check if the target is in the mid location in the array.
We then decide if we go right or left based on the `target` value and the value in the array at the midpoint.
With this new partition of the array, we make a recursive call.
/**
* Find the maximum total sweetness of the piece you can get by
* cutting the chocolate bar `optimally`.
*
* Time: O(n * log(m)) - Space: O(1)
* n = sweetness.length
* m = low .. high
*/
static public int maximizeSweetness(int[] sweetness, int k) {
// **** initialization ****
int low = 1;
int high = Arrays.stream(sweetness).sum() / (k + 1);
// **** binary search - O(log(m) ****
while (low < high) {
// ???? ????
System.out.println("maximizeSweetness <<< low: " + low + " high: " + high);
// **** compute mid ( + 1 allows us to get out of an endless loop) ****
int mid = (low + high + 1) / 2;
// ???? ????
System.out.println("maximizeSweetness <<< mid: " + mid);
// **** greedy approach ****
if (canSplit(sweetness, k, mid)) low = mid;
else high = mid - 1;
}
// **** sweetness level ****
return low;
}
This is a recursive function that implements the function of interest. Note the similarities and differences with the standard binary search.
When we decide on the midpoint to determine in which part of the array we continue our search, we call an auxiliary function that will perform the determination using a Greedy approach.
When all is said and done we return the low value. Yes, we use low and high instead of left and right.
/**
* Implementation of Greedy algorithm.
*/
static private boolean canSplit(int[] sweetness, int k, int mid) {
// **** initialization ****
int chunks = 0;
int sum = 0;
// **** O(n) ****
for (int i = 0; i < sweetness.length; i++) {
// **** update sum ****
sum += sweetness[i];
// ???? ????
// System.out.println("canSplit <<< sum: " + sum);
// **** split chocolate bar (if needed) ****
if (sum >= mid) {
chunks++;
sum = 0;
// ???? ????
// System.out.println("canSplit <<< chunks: " + chunks);
}
}
// **** we can split the chocolate bar ****
return chunks >= (k + 1);
}
This is the implementation of the Greedy algorithm.
We perform an initialization step.
We then traverse the bar from left to right. At each step we add the current sweetness and if the value in `sum` exceeds the `mid` value it is time to cut the chocolate bar. We update the number of chunks and reset the sum.
After we are done with the loop, we return true or false based on the relation between the number of chunks and the number of pieces we are looking for. Keep in mind that we need to cut enough pieces for our `k` friends and one for us.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).
This problem happens to be somewhat similar to LeetCode 410 Split Array Largest Sum. I will tackle the problem in our next post.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John