Allocate Books InterviewBit Solution

Problem: Allocate Books

Problem Description:

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 allotted 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.

Note: Return -1 if a valid assignment is not possible.

Input Format

The first argument given is the integer array A. The second argument given is the integer B. 

Output Format

Return that minimum possible number 

Constraints

1 <= N <= 10^5 
1 <= A[i] <= 10^5

For Example

Input 1:
    A = [12, 34, 67, 90]
    B = 2
Output 1:
    113
Explanation 1:
    There are 2 number of students. Books can be distributed in following fashion : 
        1) [12] and [34, 67, 90]
        Max number of pages is allocated to student 2 with 34 + 67 + 90 = 191 pages
        2) [12, 34] and [67, 90]
        Max number of pages is allocated to student 2 with 67 + 90 = 157 pages 
        3) [12, 34, 67] and [90]
        Max number of pages is allocated to student 1 with 12 + 34 + 67 = 113 pages

        Of the 3 cases, Option 3 has the minimum pages = 113.

Input 2:
    A = [5, 17, 100, 11]
    B = 4
Output 2:
    100

Approach

This problem is an unique type of binary search problem, where you don't do binary search on index, but on the range of answer.

Let's talk about the situation when there will be no valid assignment and for that answer is -1. This is possible only when, the number of students exceeds numbers of books, only then you can not allot minimum of one book to some student(s).

So now the second case, when valid answer exists for sure.

In this case the maximum possible answer is the sum of pages of all the books, given only to one student. And Let's take the minimum to be zero, even though according to the given constraints it's not possible to have 0 as an answer, but if there exists a valid answer then binary search will eventually find it.

So we have a range, from 0 to the sum of pages, we can do binary search on this range, if for a given threshold value, it is possible to assign books to students, then we shift towards left, to find minimum, otherwise to the right.

In the below solution, "canBePlaced" function tells us whether the given threshold number of pages can be distributed among the students or not. Here, threshold means, we can not allocate a student more than threshold value of pages.

Time & Space Complexity

Time Complexity: O(logN), N being the sum of array P. 

Space Complexity: O(1), Ignoring the space taken by the given input array.

Solution:

Code in C++