Last Updated: 11 Jan, 2021

Allocate Books

Hard

Asked in companies

Solve now

Problem statement

You are the Librarian of the Ninja library. There are ‘N’ books available in the library and ‘B’ ninjas want to read the books. You know the number of pages in each book and you have to allocate the books to the ‘B’ ninjas in such a way that the maximum number of pages allocated to a ninja is minimum.

Note

A book will be allocated to exactly one ninja. 
At least one book has to be allocated to a ninja.
Allotment of the books should be done in a contiguous manner. For example, a ninja can not be allocated book 2 and book 4, skipping book 3.

The task is to return the minimum of the maximum number of pages allocated to a ninja.

Input Format:

The first line contains a single integer T representing the number of test cases.      
The T-test cases are as follows:

The first line contains two space-separated integers ‘N’ and ‘B’ denoting the number of books, and the number of ninjas, respectively. 
The second line contains N space-separated integers, where the ith element is the number of pages in the ith book.

Output Format :

The first and only line of output contains an integer denoting the minimum of the maximum number of pages allocated to a ninja. 
The output of every test case is printed in a separate line.

Note:

Return -1 if it is impossible to allocate the books to all the ninjas.

Constraints:

1 <= T <= 10
1 <= N <= 10^4
1 <= B <= 10^2
0 <= pages <= 10^3

where T is the number of test cases, ‘N’ is the number of books, ‘B’ is the number of ninjas and ‘pages’ is the number of pages in each book.

Solve now

Approaches

01 Approach

Let’s look at both conditions:

When there is no valid assignment of the books and the answer is -1.
It is possible only when the number of ninjas is more than the number of books available in the library.
When we can allocate the books in a valid manner and a positive answer exists.

Let’s say the maximum possible answer is the sum of pages of all the books( say sumOfPages ), allocated only to a ninja and the minimum possible answer is the maximum number of pages in a book ( say maxPages ). Note that the minimum possible answer can not be 0 as we have to allocate something to every ninja.
Now we have a range from 'maxPages’ to ‘sumOfPages’ of all books.
We will run a loop from i = ‘maxPages’ to ‘sumOfPages’ and we will increment i with 1.
- Check whether it is possible to assign the books to all the ninjas such that the maximum possible pages allocated to a ninja is less than or equal to ‘i’.
  - If yes, we will store ‘i’ in an answer variable and break the loop as it is the minimum possible answer we can get.
  - Else, we will continue and check with more pages.
Finally, we will return the answer.

Solve now

02 Approach

Approach:

Let’s say the maximum possible answer is the sum of pages of all the books( say sumOfPages ), allocated only to a ninja and the minimum possible answer is the maximum number of pages in a book ( say maxPages ). Note that the minimum possible answer can not be 0 as we have to allocate something to every ninja.
Now we have a range from 'maxPages’ to ‘sumOfPages’ of all books. As this range is sorted, we can apply binary search technique.
We will pick the middle number from the above range and check whether it is possible to assign the books to all the ninjas such that the maximum possible pages allocated to a ninja is less than or equal to the middle number.
- If yes, we will store this number as our answer and try to minimize it further. To minimize the current answer, we will consider the range maxPages to middle.
- Else, we will try to increase this number by considering the range between middle + 1 to ‘sumOfPages’.
Finally, we will return the minimum possible answer.

Note that we can use any method for binary search( recursive / iterative ). In the code, we are using iterative binary search to improve the space complexity.

Solve now