For the DSA problem - Allocate books , the below solution fails for few of the test cases. When the line if(students==m) is removed all test cases passes. But this does not make sense , why should we store the answer when numberOfStudents(mid,arr,m) returns a number less than required students. The question mentions that all students need to be allocated books.
public class Solution {
public static int findPages(ArrayList<Integer> arr, int n, int m) {
if(arr.size()<m) return -1;
return BinarySearchSolution(arr,m,m);
}
public static int BinarySearchSolution(ArrayList<Integer> arr, int n, int m){
int max = -1;
int sum= 0;
for(int i:arr){
max = Math.max(i,max);
sum+=i;
}
int low = max,high=sum;
int ans=Integer.MAX_VALUE;
while(low<=high){
int mid =(low + high) /2;
int students = numberOfStudents(mid,arr,m);
if(students<=m){
high=mid-1;
if(students==m) ans=mid;
}else{
low = mid+1;
}
}
return ans;
}
public static int numberOfStudents(int limit,ArrayList<Integer> arr, int m){
int currentPagesSum = 0;
int students = 0;
for(int i=0;i<arr.size();i++){
if(arr.get(i) + currentPagesSum <=limit ){
currentPagesSum +=arr.get(i);
}else{
students++;
currentPagesSum=0;
i--;
}
}
return students+1;
}
}