Hello TA good morning,
IN this problem basically, we are doing binary with start as the largest element in the array and end as the sum of elements in the array but the Prateek bhaiyaa told in his lecture that the code will be fine if we start the binary search operation with start =0 and last =sum of elements instead of starting with the largest element but what I found was if I start with the first as 0 I am getting incorrect and for many cases and my code is also not getting accepted can you tell me the reason why its happening;
below I have attached my code:-
#include
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool cando(int a[],int n,int m,int mid){
int student=1;
int count=0;
for(int i=0;i<n;i++){
if(count+a[i]>mid){
student++;
count=a[i];
if(student>m){
return false;
}
}
else{
count+=a[i];
}
}
return true;
}
int checkif(int arr[],int n,int m)
{
int sum=0;
for(int i=0;i<n;i++)
{
sum=sum+arr[i];
}
int start=0,end=sum,ans=0;
while(start<=end)
{int mid=start+(end-start)/2;
if(cando(arr,n,m,mid)){
ans=mid;
end=mid-1;
}
else{
start=mid+1;
}
}
cout<<ans<<endl;
return 0;
}
int main()
{
int k;
cin>>k;
while(k–)
{
ll n,m;
cin>>n>>m;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
checkif(arr,n,m);
}
}
Thanks