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/

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions