Lintcode 1817. Divide Chocolate

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

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]

Notice

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

 

Solution:

Binary search on answer. 

The idea is if we give a larger sweetness to each person, they tend to have more pieces each one, so the number of people we can distribute tend to be less. The same to the other. If a person gets less sweetness, we can distribute to more people.

So the idea is, given a sweetness level, we can find out the number of people we can distribute to. If it's less than the K + 1, that means the sweentess we choose was too high; otherwise, if the number of people is greater or equal to the K + 1, we can try a bigger sweetness.

Code (Java):

public class Solution {
    /**
     * @param sweetness: an integer array
     * @param K: an integer
     * @return:  return the maximum total sweetness of the piece
     */
    public int maximizeSweetness(int[] sweetness, int K) {
        // write your code here
        if (sweetness == null || sweetness.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = 0;
        
        for (int s : sweetness) {
            lo = Math.min(lo, s);
            hi += s;
        }
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (getNumFriends(sweetness, mid) >= K + 1) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        
        if (getNumFriends(sweetness, hi) >= K + 1) {
            return hi;
        }
        
        return lo;
    }
    
    private int getNumFriends(int[] sweetness, int s) {
        int count = 0;
        int curr = 0;
        
        for (int sweet : sweetness) {
            curr += sweet;
            if (curr >= s) {
                count++;
                curr = 0;
            }
        }
        
        return count;
    }
}