Problem

Submissions

Hints & solutions

Discuss

Allocate Books

Moderate

0/80

Average time to solve is 10m

969 upvotes

Asked in companies

Problem statement

Given an array ‘arr’ of integer numbers, ‘arr[i]’ represents the number of pages in the ‘i-th’ book.

There are ‘m’ number of students, and the task is to allocate all the books to the students.

Allocate books in such a way that:

1. Each student gets at least one book.
2. Each book should be allocated to only one student.
3. Book allocation should be in a contiguous manner.

You have to allocate the book to ‘m’ students such that the maximum number of pages assigned to a student is minimum.

If the allocation of books is not possible, return -1.

Example:

Input: ‘n’ = 4 ‘m’ = 2 
‘arr’ = [12, 34, 67, 90]

Output: 113

Explanation: All possible ways to allocate the ‘4’ books to '2' students are:

12 | 34, 67, 90 - the sum of all the pages of books allocated to student 1 is ‘12’, and student two is ‘34+ 67+ 90 = 191’, so the maximum is ‘max(12, 191)= 191’.

12, 34 | 67, 90 - the sum of all the pages of books allocated to student 1 is ‘12+ 34 = 46’, and student two is ‘67+ 90 = 157’, so the maximum is ‘max(46, 157)= 157’.

12, 34, 67 | 90 - the sum of all the pages of books allocated to student 1 is ‘12+ 34 +67 = 113’, and student two is ‘90’, so the maximum is ‘max(113, 90)= 113’.

We are getting the minimum in the last case.

Hence answer is ‘113’.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line contains two space-separated integers ‘n’ denoting the number of books and ‘m’ denotes the number of students. 

The second line contains ‘n’ space-separated integers denoting the number of pages in each of ‘n’ books.

Output Format:

Return the integer as described above.

Note:

Do not print anything, just return the maximum number of pages that are assigned to a student is minimum.

Sample Input 1:

4 2
12 34 67 90

Sample Output 1:

Explanation of sample input 1:

All possible ways to allocate the ‘4’ books to '2' students are:

12 | 34, 67, 90 - the sum of all the pages of books allocated to student 1 is ‘12’, and student two is ‘34+ 67+ 90 = 191’, so the maximum is ‘max(12, 191)= 191’.

12, 34 | 67, 90 - the sum of all the pages of books allocated to student 1 is ‘12+ 34 = 46’, and student two is ‘67+ 90 = 157’, so the maximum is ‘max(46, 157)= 157’.

12, 34, 67 | 90 - the sum of all the pages of books allocated to student 1 is ‘12+ 34 +67 = 113’, and student two is ‘90’, so the maximum is ‘max(113, 90)= 113’.

We are getting the minimum in the last case.

Hence answer is ‘113’.

Sample Input 2:

5 4
25 46 28 49 24

Sample Output 2:

Explanation of sample input 2:

All possible ways to allocate the ‘5’ books to '4' students are:

25 | 46 | 28 | 49 24 - the sum of all the pages of books allocated to students 1, 2, 3, and 4 are '25', '46', '28', and '73'. So the maximum is '73'.

25 | 46 | 28 49 | 24 - the sum of all the pages of books allocated to students 1, 2, 3, and 4 are '25', '46', '77', and '24'. So the maximum is '77'.

25 | 46 28 | 49 | 24 - the sum of all the pages of books allocated to students 1, 2, 3, and 4 are '25', '74', '49', and '24'. So the maximum is '74'.

25 46 | 28 | 49 | 24 - the sum of all the pages of books allocated to students 1, 2, 3, and 4 are '71', '28', '49', and '24'. So the maximum is '71'.

We are getting the minimum in the last case.

Hence answer is ‘71’.

Expected time complexity:

The expected time complexity is O(n * log(s)), where ‘n’ is the number of integers in the array ‘arr’ and ‘s’ is the sum of all the elements of ‘arr’.

Constraints:

2 <= 'n' <= 10 ^ 3
1 <= 'm' <= 10 ^ 3
1 <= 'arr[i]' <= 10 ^ 9
The sum of all arr[i] does not exceed 10 ^ 9.

Where ‘n’ denotes the number of books and ‘m’ denotes the number of students. ‘arr[i]’ denotes an element at position ‘i’ in the sequence.

Time limit: 1 second

Hint 1

Hint 2

Try all possible minimum number of pages.

Approaches (2)

Approach 1

Approach 2

Linear Search

The basic idea is that, try each and every possible value that can be answered. It can be from ‘1’ to the sum of ‘arr’.

Find the sum of all the elements of ‘arr’ in a variable ‘sum’.
Iterate a loop ‘i’ from ‘1’ to ‘sum’(inclusive).
Check for every ‘i’, if it is possible to divide the at least ‘i’ pages to every student.
- If possible then return ‘i’ because we are iterating from minimum then it is the minimum answer.
- Else check for ‘i+1’.
If the number of ‘n<m’ then return ‘-1’, because the number of students is more than the number of books.

How to check - if it is possible to divide at least ‘mid’ number of pages in each student

Iterate a loop ‘i’, if sum of some contiguous books pages is less than or equals to mid then assign this sou to a single student and check for remain student and at the end if is possible then can say it is possible that ‘mid’ number of pages is possible to assign ‘m’ student.

Time Complexity

O(n * s), where ‘n’ is the number of integers in the array ‘arr’ and ‘s’ is the sum of all the elements of ‘arr’.

We are using two nested loops of size ‘s’ and ‘n’.

Therefore the time complexity is O(n * s).

Space Complexity

O(1)

We are using constant space.

Therefore the space complexity is O(1).

(75% EXP penalty)

(100% EXP penalty)

Allocate Books

Lakshita

Interview problems

Easy Binary Search Approach

int solve(vector<int>& arr, int n, int mid){

int stu=1, load=0;

for(int i=0; i<n; i++){

if(arr[i]+load>mid){

load = arr[i];

stu++;

}

else{

load +=arr[i];

}

return stu;

}

int findPages(vector<int>& arr, int n, int m) {

// Write your code here.

if(m>n)return -1;

int sum =0, maxi = INT_MIN;

for(int i=0; i<n; i++){

sum+=arr[i];

maxi = max(maxi, arr[i]);

}

int ans =-1;

int low = maxi, high = sum;

while(low<=high){

int mid = low+(high-low)/2;

int stu = solve(arr, n, mid);

if(stu <=m){

ans = mid;

high = mid-1;

}

else{

low = mid+1;

}

return ans;

}

62 views

0 replies

0 upvotes

Ansh

Interview problems

easy ,simple and basic cpp code

bool isPossible(vector<int>& arr, int n, int m, int mid) {

int studentCount = 1;

int pageSum = 0;

for (int i = 0; i < n; i++) {

if (pageSum + arr[i] <= mid) {

pageSum += arr[i];

} else {

studentCount++;

if (studentCount > m || arr[i] > mid) {

return false;

}

pageSum = arr[i];

}

return true;

}

int findPages(vector<int>& arr, int n, int m) {

if (m > n) return -1;

int sum = 0;

int maxElem = arr[0];

for (int i = 0; i < n; i++) {

sum += arr[i];

maxElem = max(maxElem, arr[i]);

}

int low = maxElem;

int high = sum;

int result = -1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (isPossible(arr, n, m, mid)) {

result = mid;

high = mid - 1;

} else {

low = mid + 1;

}

return result;

}

165 views

0 replies

0 upvotes

srinivas lingampelli

Interview problems

Simple || java || Binary Search || Understanding the Role of <= m in Book Allocation Using Binary Search"

import java.util.ArrayList;
public class Solution {

    public static int allocateBooks(ArrayList<Integer> arr,int pages)
    {
            int students=1;
            int pageStudents=0;

            for(int i=0;i<arr.size();i++)
            {
                if(pageStudents+arr.get(i)<=pages)
                {
                    pageStudents=pageStudents+arr.get(i);
                }
                else{
                    pageStudents=arr.get(i);
                    students++;
                }
            }
            return students;
    }
    public static int findPages(ArrayList<Integer> arr, int n, int m) {
        // Write your code here.
        int max=Integer.MIN_VALUE;
        int sum=0;


        for(int i=0;i<arr.size();i++)
        {
            sum=sum+arr.get(i);
            if(arr.get(i)>max)
            {
                max=arr.get(i);
            }
        }
        if(m==1)
        {
            return sum;

        }
        if(m>n)
        {
            return -1;
        }

        // System.out.println(max);
        // System.out.println(sum);

        int left=max;
        int right=sum;
        int ans=-1;
        while(left<=right)
        {
            int mid=(left+right)/2;

            if(allocateBooks(arr,mid)<=m)
            {
                ans=mid;
                right=mid-1;

            }
            else{
                left=mid+1;
            }

        }
        
        return ans;

    }
}

94 views

0 replies

0 upvotes

Aman Raj

Interview problems

Binary Search

int checkPage(vector<int> &arr, int targetPage){

int pageCount = 0, studCount = 1 ;

for(auto it: arr){

if(it+pageCount<=targetPage)

pageCount += it;

else{

studCount++;

pageCount = it;

}

return studCount;

}

int findPages(vector<int>& arr, int n, int m) {

// Write your code here.

if(n<m) return -1;

int st = *max_element(arr.begin(), arr.end());

int end = accumulate(arr.begin(), arr.end(), 0);

while(st<=end){

int mid = st+(end-st)/2;

int studCount = checkPage(arr, mid);

if(studCount > m ) st = mid+1;

else end = mid-1;

}

return st;

}

115 views

0 replies

0 upvotes

Ankita Paul

Interview problems

Easy C++ Code || Binary Search Technique

bool isvalid(vector <int> &arr, int n, int m,int maxAllocatePages){
    int stu=1,pages=0;
    for(int i=0;i<n;i++){
        if(arr[i]>maxAllocatePages)  return false;
        if(pages+arr[i] <= maxAllocatePages)  pages+=arr[i];
        else {
          stu++;
          pages=arr[i];
        }
    }

    return stu > m ? false :true;
}



int findPages(vector<int>& arr, int n, int m) {
    // Write your code here.
    //base case
    if(m > n){
        return -1;
    }
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=arr[i];
    }

    int ans=-1;
    int st=0,end=sum;   //range of possible ans
    //binary search
    while(st<= end){
        int mid=st+(end-st)/2;
        if(isvalid(arr,n,m,mid)){ //left
            ans=mid;
            end=mid-1;
        }
        else{  //right
            st=mid+1;
        }
    }
    return ans;
}

127 views

0 replies

1 upvote

Sunny yadav

Interview problems

Tip : if (m>n ) then return -1

int sum(vector <int> &vec)

{

int sum=0;

for (int i = 0; i < vec.size(); i++)

{

sum+=vec[i];

}

return sum;

}

bool is_possible_solution(vector <int> &vec,int mid,int n)

{ // 10 20 30 40

int ans=mid,sum1=0,i;int c=1;

for ( i = 0; i < vec.size(); i++)

{

if(c<=n)

{

if(ans>=sum1+vec[i])

{

sum1+=vec[i];

}

else

{

sum1=0;

i--;

c++;

}

if (sum1==0)

{

return false;

}

else return true;

}

int binary_soln(vector <int> &vec,int n)

{

int st=0;

int end=sum(vec);int ans=-1;

int mid=st + (end-st)/2;

while (st<=end)

{

if(is_possible_solution(vec,mid,n))

{

ans=mid;

// cout<<ans<<endl;

end=mid-1;

}

else

{

st=mid+1;

// cout<<st<<endl;

}

mid=st + (end-st)/2;

}

return ans;

}

int findPages(vector<int>& arr, int n, int m) {

if(m>n) return -1;

else return binary_soln(arr,m);

}

24 views

0 replies

0 upvotes

Mohd Mohtashim Nawaz

Interview problems

Wrong condition or wrong test case

As per the question, each student must get at least one book. That means the correct answer shall have all the books allocated to all the students.

But in test case #10, the answer `10` is found with the condition that numOfStudents≤m rather than numOfStudents==m. This doesn't seem right.

30 views

0 replies

3 upvotes

Amit Gupta

Interview problems

Book allocate||C++

bool isPossible(vector<int>& arr,int n,int m,int mid) {

int student=1;

int pages=0;

for(int i=0; i<n; i++) {

if(pages+arr[i]<=mid) {

pages+=arr[i];

}

else {

student++;

if(student>m||arr[i]>mid) {

return false;

}

pages=arr[i];

}

return true;

}

int findPages(vector<int>& arr, int n, int m) { if(m>n){ return -1; } int s=0;

int sum=0;

for(int i=0; i<n; i++) {

sum=sum+arr[i];

}

int e=sum;

int mid=s+(e-s)/2;

int ans=-1;

while(s<=e) {

if (isPossible(arr,n,m,mid)) {

ans=mid;

e=mid-1;

} else {

s=mid+1;

}

mid=s+(e-s)/2;

}

return ans; }

97 views

0 replies

2 upvotes

Diwakar Singh

Interview problems

Best solution

bool isPossibleSolution(vector<int>& arr, int n, int m, int mid) {

int studentCount = 1;

int pageSum = 0;

for(int i = 0; i<n; i++) {

if (pageSum + arr[i] <= mid) {

pageSum += arr[i];

}

else {

studentCount++ ;

if(studentCount > m || arr[i] > mid) {

return false;

}

pageSum = arr[i];

}

return true;

}

int findPages(vector<int>& arr, int n, int m) {

if (m>n){ //for the case when book allocation is not possible

return -1;

}

int s = 0 ;

int sum = 0;

for(int i = 0; i<n; i++) {

sum += arr[i];

}

int e = sum;

int ans = -1;

int mid = s + (e-s)/2;

while(s<=e) {

if(isPossibleSolution(arr,n,m,mid)){

ans = mid;

e = mid - 1;

}

else {

s = mid + 1;

}

mid = s + (e-s)/2;

}

return ans;

}

196 views

0 replies

0 upvotes

Kalki Dang

Interview problems

Good Sol

int possible(int mid,vector<int>&arr){

long long pages=0;

int students=0;

for(int i=0;i<arr.size();i++){

if(pages+arr[i]<=mid){

pages+=arr[i];

}else{

students++;

pages=arr[i];

}

return students+1;

}

int findPages(vector<int>& arr, int n, int m) {

// Write your code here.

if(m>n){

return -1;

}

int maxi=INT_MIN;

int sum=0;

for(int i=0;i<arr.size();i++){

maxi=max(maxi,arr[i]);

sum+=arr[i];

}

int low=maxi;

int high=sum;

int ans=-1;

while(low<=high){

int mid=(low+high)/2;

if(possible(mid,arr)<=m){

ans=mid;

high=mid-1;

}else{

low=mid+1;

}

return ans;

}

101 views

0 replies

0 upvotes

Console