Leetcode discuss: 1231. Divide Chocolate

 Here is the link. 

First practice - C# - Binary Search - Deadloop concern

Dec. 7, 2020
Introduction
It took me at least 10 minutes to understand what is asking for. I like to rephrase the requirement and see if I can figure out next time in less than one minutes.

Requirement statement
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]

You will cut the chocolate in K + 1 pieces, any piece should include one or more than one consecutive numbers in the array. You will take the minimum sweatness piece, and you will try to make your piece maximum.

What is your maximum sweetness?

Test case deadloop
I ran into test case deadloop for the test caes [1, 2, 3, 4, 5, 6, 7, 8, 9], k = 5.
start = middle, middle = 5, and then I checked the code I studied, and I added one in the definition of middle.

 int middle = start + (end - start + 1)/ 2;

I want to make sure that if start = 5, end = 6, middle = 6 not 5, otherwise middle = 5, go to deadloop.

Binary search
I did come out the idea to use binary search, even I read lee215's post but I could not figure out. After I read the discussion post with the source code here, I quickly understood binary search is the solution.

public class Solution {
    public int MaximizeSweetness(int[] sweetness, int K) {
        K = K + 1; // Include yourself.
        
        int start = sweetness.Min();
        int end  = sweetness.Sum();
        
        while (start < end) {
            int middle = start + (end - start + 1)/ 2;
            
            if (split(sweetness, middle) < K) 
            {
                end = middle - 1;
            } 
            else 
            {
                start = middle; // include middle
            }
        }
        
        return start;
    }

    /// make sure every cut is at least minSweetness
    private int split(int[] arr, int minSweetness) {
        int peopleCount = 0;
        int sweetness = 0;
        
        foreach (int val in arr) {
            sweetness += val;
            
            if (sweetness >= minSweetness) {
                peopleCount++;
                sweetness = 0;
            }
        }
        
        return peopleCount;
    }    
}