BINARY SEARCH | Competitive Programming Lecture-2

[dheerjain]

I think here a better way to write the time complexity will be according to the Master's Theorem
T(W)=T(W/2)+O(n)====> W=s-e+1. This gives TC as O(n) according to master's theorem

[tooTiredForThisLife]

Instead of assigning end with Int.max value, we can put the sum of weights as end, right? Because it will be the maximum minimum capacity required for a certain input like D=1

[sunnygupta]

package binary;

public class allocateminbooks {
static int allocate(int arr[], int k)
{
int maxnum=0;int maxsum=0; int res=0;
for(int v:arr)
{
maxsum+=v;
maxnum=Math.max(maxnum, v);
}
if(arr.length==k)return maxnum;
int low=maxnum;int high=maxsum;
while(low<=high)
{
int mid=low+(high-low)/2;
if(isvalid(arr, mid, k)==true)
{
res=mid;
high=mid-1;
}
else
{
low=mid+1;
}
}
return res;
}
static boolean isvalid(int arr[], int cap, int k)
{
int student=1;
int books=0;
for(int i=0;i<arr.length;i++)
{
books+=arr[i];
if(books>cap)
{
student++;
books=arr[i];
}

}
return student<=k;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.out.println(allocate(arr, 2));

}

}






isme kya galti hai koi bata sakta hai kya plz, i am trying to run same code in this problem too but not giving correct ans

[kunalmakwana]

Are you going to cover all topics of cp ?