Allocate books DSA problem - Why is storing answer necessary when books allocated to less students?

40 Views Asked by At

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;
    }


}
0

There are 0 best solutions below