Divide Chocolate LeetCode Solution

Difficulty Level Hard
Frequently asked in Amazon Facebook Google
Array Binary SearchViews 3186

Problem Statement

The Divide Chocolate LeetCode solution says the chocolate bar is represented by a list of non-zero integers.

The sum of a contiguous subarray stands for the sweetness of the chocolate piece represented by this subarray.

Here the task is to find the maximum possible minimum sum of all subarrays after dividing the array into k + 1 contiguous subarrays.

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]

 

Approach

Idea

  1. This problem can be solved by the binary search method.
  2. Our search space will be from 1 to total_sweetness_value/(k+1) or we make our right-hand limit to 1e9 as it never harms our answer.
  3. Check if we can cut the chocolate into k + 1 pieces with sweetness no less than, where mid is our current guess at the optimal workable value.
  4. Now we have to take a decision according to our estimated value in the check function, if our cnt score is greater than equals (k+1) we can increase l=mid+1, else r=mid-1.

Code

Divide Chocolate C++ Solution

class Solution {
public:
    #define ll long long
    vector<int>a;
    ll check(ll mid,ll k)
    {
        ll i,n=a.size();
        ll sum=0,cnt=0;
        for(i=0;i<n;i++)
        {
            sum+=a[i];
            if(sum>=mid)
            {
                cnt++;
                sum=0;
            }
        }
        return cnt>=(k+1);
    }
    int maximizeSweetness(vector<int>& sweetness, int k) {

        a=sweetness;
        ll l=1,r=1e9,mid,ans;
        while(l<=r)
        {
            mid=l+(r-l)/2;
            if(check(mid,k))
            {
                l=mid+1;
                ans=mid;
            }
            else
                r=mid-1;
        }
        return ans;
    }
};

Divide Chocolate Java Solution

class Solution {
    int a[];
    int check(int mid,int k)
    {
        int i,n=a.length;
        int sum=0,cnt=0;
        for(i=0;i<n;i++)
        {
            sum+=a[i];
            if(sum>=mid)
            {
                cnt++;
                sum=0;
            }
        }
        if(cnt>=(k+1))
            return 1;
        return 0;
    }
    public int maximizeSweetness(int[] sweetness, int k) {
        a=sweetness;
        long l=1,mid,ans=0;
        long r = (long) Math.pow(10, 9);

        while(l<=r)
        {
            mid=l+(r-l)/2;
            if(check((int)mid,(int)k)==1)
            {
                l=mid+1;
                ans=mid;
            }
            else
                r=mid-1;
        }
        return (int)ans;
    }
}

Complexity Analysis of Divide Chocolate LeetCode Solution

Time Complexity

Time Complexity is O(NlogS). N is the size of the array. S is the total sweetness.

Space Complexity

As we can see no extra space is used. So it will be O(1).

Translate »