Allocate Books

Hard
0/120
58 upvotes
Asked in companies
ZSArcesiumAdobe

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.

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

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.

Sample Input 1:

1
4 2
10 20 30 40

Sample output 1:

60

Explanation of Sample output 1:

There are two ninjas and these are the following ways to allocate the books between them. 
Way 1 ⇒ Ninja 1: [10] and Ninja 2: [20, 30, 40] 
Way 2 ⇒ Ninja 2: [10, 20], and Ninja 2: [30, 40] 
Way 3 ⇒ Ninja 1: [10, 20, 30], and Ninja 2: [40] 
Among all the ways, way 3 is the best way because the maximum number of pages allocated to a ninja is 60. In way 1 and way 2, the maximum number of  pages allocated to a ninja is 90, and 70, respectively. Hence, 60 is the answer.

Sample Input2:

1
5 6
10 20 30 40 50

Sample Output2:

-1

Explanation of Sample output 2

Since we can not allocate at-least one book to every ninja, the answer is -1.
Hint

Consider all the possible ways. 

Approaches (2)
Brute force

Let’s look at both conditions:

  1. 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.
  2. 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.
Time Complexity

O(N * sumOfPages), where N is the number of books and ‘sumOfPages’ is the sum of the pages of all the books. 

We are looping on a range(‘maxPages’ to ‘sumOfPages’)[ O(sumOfPages) time] and for every index, we are checking if 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 current index [O(N) time]. Thus, the final time complexity is O(N) * O(sumOfPages) = O(N * sumOfPages).

Space Complexity

O(1)

Constant additional space is used.

Code Solution
(100% EXP penalty)
Allocate Books
Full screen
Console