# Fair Distribution of Chocolates

Binary Search

Hard

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given number of chocolates in `N` different bags and `M` children. Every kid will get some consecutive bags. The task is to distribute chocolates in such a way that the maximum number of chocolates assigned to a kid is `minimum`.

See original problem statement here

EXAMPLE :

``````Input : chocolates[] = {12, 34, 67, 90}
M = 2

Output : 113

Explanation:

There are 2 kids. Chocolates can be distributed in following fashion :

1)  and [34, 67, 90]
Max number of chocolates is allocated to kid
2 with 34 + 67 + 90 = 191 chocolates

2) [12, 34] and [67, 90]
Max number of chocolates is allocated to kid
2 with 67 + 90 = 157 chocolates

3) [12, 34, 67] and 
Max number of chocolates is allocated to student
1 with 12 + 34 + 67 = 113 chocolates

Of the 3 cases, Option 3 has the minimum chocolates = 113. ``````

#### SOLVING APPROACH:

1. The idea is to use `Binary Search` according to data structures in c++.

2. We initialize `minimum` and `maximum` as `0` and `sum-of-all-chocolates` respectively.

3. We fix a value for the number of chocolates as `mid` of current `minimum` and `maximum`.

4. If a current `mid` can be a feasible solution, then we search on the lower half, else we search in higher half.

5. Before that we need to check if `mid` value is feasible or not.

6. Basically, we need to check if we can distribute chocolates to all children in a way that the maximum number doesn’t exceed current value. To do this, we sequentially assign chocolates to every kid while the current number of assigned chocolates doesn’t exceed the value.

7. In this process, if the number of kids becomes more than `M`, then the solution is not feasible. Else feasible.

#### SOLUTIONS:

```
#include <stdio.h>
#include <limits.h>

//function for finding if assumed minimum is possible or not
int isPossible(int *arr, int n, int m, long long curr_min){

long long  curr_sum = 0;
int studentRequired = 1;
for(int i=0; i<n; i++){
/* if any value in array is greater than current minimum
value then it is not a valid value and therefore return */
if(arr[i] > curr_min)
return 0;

if(arr[i] + curr_sum > curr_min){

studentRequired++;
curr_sum = arr[i];
/* if at any point required student becomes greater
than actual student return false */
if(studentRequired > m)
return 0;
}
else{
curr_sum += arr[i];
}
}
return 1;
}

long long solution(int *arr, int n, int m){

long long  sum = 0;
//finding sum of all elements
for(int i=0 ;i<n; i++)
sum += arr[i];

//if books are less than students
if(n < m)
return -1;

//assume minimum pages to be start and maximum pages to be end
int start = 0;
int end = sum;

long long result = LLONG_MAX;

while(start <= end){
//we assume that this mid value can be our minimum pages
long long mid = start + (end - start) / 2;

/* if mid value is possible, store it and
go on searching for a lower value of mid */
if(isPossible(arr, n, m, mid)){

if(mid < result)
result = mid;
end = mid - 1;
}
/* if not possible search in the right half
for a possible value */
else{
start = mid + 1;
}
}
return result;
}

int main()
{
int t; scanf("%d", &t);
while(t--){
int n, k; scanf("%d", &n);
int arr[n];
for(int i=0; i<n; i++){
scanf("%d", &arr[i]);
}
scanf("%d", &k);

printf("%lld\n", solution(arr, n, k));
}
return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;

//function for finding if assumed minimum is possible or not
int isPossible(int *arr, int n, int m, long long curr_min){

long long  curr_sum = 0;
int studentRequired = 1;
for(int i=0; i<n; i++){
/* if any value in array is greater than current minimum
value then it is not a valid value and therefore return */
if(arr[i] > curr_min)
return 0;

if(arr[i] + curr_sum > curr_min){

studentRequired++;
curr_sum = arr[i];
/* if at any point required student becomes greater
than actual student return false */
if(studentRequired > m)
return 0;
}
else{
curr_sum += arr[i];
}
}
return 1;
}

int solution(int *arr, int n, int m){

long long  sum = 0;
//finding sum of all elements
for(int i=0 ;i<n; i++)
sum += arr[i];

//if books are less than students
if(n < m)
return -1;

//assume minimum pages to be start and maximum pages to be end
int start = 0;
int end = sum;

long long result = INT_MAX;

while(start <= end){
//we assume that this mid value can be our minimum pages
long long mid = start + (end - start) / 2;

/* if mid value is possible, store it and
go on searching for a lower value of mid */
if(isPossible(arr, n, m, mid)){

result = min(result, mid);
end = mid - 1;
}
/* if not possible search in the right half
for a possible value */
else{
start = mid + 1;
}
}
return result;
}

int main()
{
int t; cin>>t;
while(t--){
int n, k; cin>>n;
int arr[n];
for(int i=0; i<n; i++){
cin>>arr[i];
}
cin>>k;

cout<<solution(arr, n, k)<<"\n";
}
return 0;
}
```
```
import java.util.*;
import java.io.*;

public class Main {

//function for finding if assumed minimum is possible or not
static boolean isPossible(int []arr, int n, int m, long curr_min){

long curr_sum = 0;
int studentRequired = 1;
for(int i=0; i<n; i++){
/* if any value in array is greater than current minimum
value then it is not a valid value and therefore return */
if(arr[i] > curr_min)
return false;

if(arr[i] + curr_sum > curr_min){

studentRequired++;
curr_sum = arr[i];
/* if at any point required student becomes greater
than actual student return false */
if(studentRequired > m)
return false;
}
else{
curr_sum += arr[i];
}
}
return true;
}

static long solution(int []arr, int n, int m){

long  sum = 0;
//finding sum of all elements
for(int i=0 ;i<n; i++)
sum += arr[i];

//if books are less than students
if(n < m)
return -1;

//assume minimum pages to be start and maximum pages to be end
long start = 0;
long end = sum;

long result = Long.MAX_VALUE;

while(start <= end){
//we assume that this mid value can be our minimum pages
long mid = start + (end - start) / 2;

/* if mid value is possible, store it and
go on searching for a lower value of mid */
if(isPossible(arr, n, m, mid)){

result = Math.min(result, mid);
end = mid - 1;
}
/* if not possible search in the right half
for a possible value */
else{
start = mid + 1;
}
}
return result;
}

public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t != 0){
int n  = sc.nextInt();
int arr[] = new int[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
int k  = sc.nextInt();
System.out.println(solution(arr, n, k));
t--;
}
}
}
```