Home » Interview coding problems/challenges

Book Allocation Problem (Allocate minimum number of pages)

Book Allocation Problem: Here, we are going to learn the solution to book allocation problem that has been featured in coding rounds of many companies as Google, Codenation etc.
Submitted by Divyansh Jaipuriyar, on June 24, 2020

Problem statement

Given an array of integers A of size N and an integer B. College library has N bags, the ith book has A[i] number of pages.

You have to allocate books to B number of students so that the maximum number of pages allocated to a student is minimum. A book will be allocated to exactly one student. Each student has to be allocated at least one book. Allotment should be in contiguous order, for example, A student cannot be allocated book 1 and book 3, skipping book 2. Calculate and return that minimum possible number. Return -1 if a valid assignment is not possible.

Input

The first line contains T denoting the number of test cases. Then follows a description of T test cases: Each case begins with a single positive integer N denoting the number of books. The second line contains N space-separated positive integers denoting the pages of each book. And the third line contains another integer B, denoting the number of students.

Output

For each test case, output a single line containing the minimum number of pages each student has to read for the corresponding test case.

Examples

INPUT:
T=1
N=4
[10,20,30,40]
B=2

OUTPUT:	
60, one student assigned 60 pages and other 40.

INPUT:
T=1
N=4
[12 34 67 90]
B=2

OUTPUT:
113, one student assigned 113 pages and other 90.

Solution Approach (Binary Search Approach)

We will use the logic that the pages can be assigned in increasing order manner since one student can have the maximum number of pages as the sum of pages of all the books (which is practically not possible here as we need to assign something to every candidate) and to divide the page in an optimal manner we need to have a max of all the pages of different books to be assigned to some student and remaining pages should be distributed to other students so that the maximum amount of pages assigned to a student is minimum.

So the constraint for binary search start and end is solved by taking start as the max of pages of the given book and end will be the sum of all the pages from all books.
We will keep using the binary search method and each time we take mid as the pivot we check if that is the maximum number of pages which can be assigned to the B number of student optimally.

We declare a bool function isValid which will check if the current number of pages that we pass into it is a valid case of not is it satisfy the condition then we return true and then check the maximum of currently assigned pages and new assigned pages.
One more condition to check is the number of students and the number of books if the number of students is greater than the number of books then we return false to isValid condition.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// boolean function to check if the num 
// pages is valid partition or not
bool isValid(ll book[], ll n, ll sum, ll B) 
{
    // if number of books is less than number of student.
    if (n < B) 
        return false;
    else {
        // initiailse cur for number of pages 
        // that student can have.
        ll cur = 0; 
        // initialise number student count for 
        // assigned number of pages.
        ll cnt = 1; 

        for (ll i = 0; i < n; i++) {
            cur += book[i];
            // if(cur number of pages is greater than num number 
            // of pages that one student can have then we incrase 
            // the number of student by one and start again with 
            // current number of pages.
            if (cur > sum) 
            {
                cnt++;
                cur = book[i];
                // if number of student is greater than B than 
                // return false.
                if (cnt > B) 
                    return false;
            }
        }
        // if allocation is possible then return true.
        if (cnt <= B) 
            return true;
    }
    return false;
}

int main()
{
    ll t;
    
    cout << "Enter number of test cases: ";
    cin >> t;
    
    while (t--) {
        ll n;
    
        cout << "Enter number of books: ";
        cin >> n;
    
        ll book[n];
    
        cout << "Enter book pages: ";
        for (ll i = 0; i < n; i++)
            cin >> book[i];
    
        ll B;
    
        cout << "Enter number of students: ";
        cin >> B;
    
        // initialise st for binary search as 
        // the maximum value among the book.
        ll st = *max_element(book, book + n); 
    
        // initialisze end for binary search as 
        // the sum of all the values of books.
        ll end = accumulate(book, book + n, 0); 
        ll ans = INT_MAX;
    
        while (st <= end) {
            // find mid of binary search.
            ll mid = st + (end - st) / 2; 
            // check for valid condition then assign the answer.
            if (isValid(book, n, mid, B)) 
            {
                ans = mid;
                end = mid - 1;
            }
            else
                st = mid + 1;
        }

        if (ans == INT_MAX) {
            cout << "Allocation not possible: ";
            cout << -1 << "\n";
        }
        else {
            cout << "Minimum number of pages: ";
            cout << ans << "\n";
        }
    }
    
    return 0;
}

Output

Enter number of test cases: 4
Enter number of books: 4
Enter book pages: 10 20 30 40
Enter number of students: 2
Minimum number of pages: 60
Enter number of books: 4                       
Enter book pages: 12 34 67 90
Enter number of students: 2
Minimum number of pages: 113
Enter number of books: 5
Enter book pages: 25 46 28 49 24
Enter number of students: 4
Minimum number of pages: 71
Enter number of books: 3
Enter book pages: 20 20 20 
Enter number of students: 3
Minimum number of pages: 20

• Time Complexity for above approach in worst case: O(N*log(sum(book[]))
• Space Complexity for the above approach is: O(1)

---

Also tagged in: Google, Codenation

Problem source: https://www.interviewbit.com/problems/allocate-books/