# Divide Chocolate LeetCode Solution

Difficulty Level Hard
Array Binary SearchViews 1550

## 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], , , , 
```

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 »