Last Updated on March 21, 2022 by Ria Pathak
CONCEPTS USED:
Binary Search
DIFFICULTY LEVEL:
Hard
PROBLEM STATEMENT(SIMPLIFIED):
Given number of chocolates in
Ndifferent bags andMchildren. 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 isminimum.
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) [12] 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 [90]
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:
The idea is to use
Binary Search.We initialize
minimumandmaximumas0andsum-of-all-chocolatesrespectively.We fix a value for the number of chocolates as
midof currentminimumandmaximum.If a current
midcan be a feasible solution, then we search on the lower half, else we search in higher half.Before that we need to check if
midvalue is feasible or not.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.
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--;
}
}
}
Space Complexity is O(1)
[forminator_quiz id="1532"]
So, in this blog, we have tried to explain binary search. If you want to solve more questions on Searching, which are curated by our expert mentors at PrepBytes, you can follow this link Searching.