# Allocate Books

Moderate
0/80
Average time to solve is 10m

## Problem statement

Given an array βarrβ of integer numbers, βarr[i]β represents the number of pages in the βi-thβ book.

There are βmβ number of students, and the task is to allocate all the books to the students.

Allocate books in such a way that:

``````1. Each student gets at least one book.
2. Each book should be allocated to only one student.
3. Book allocation should be in a contiguous manner.
``````

You have to allocate the book to βmβ students such that the maximum number of pages assigned to a student is minimum.

If the allocation of books is not possible, return -1.

Example:
``````Input: βnβ = 4 βmβ = 2
βarrβ = [12, 34, 67, 90]

Output: 113

Explanation: All possible ways to allocate the β4β books to '2' students are:

12 | 34, 67, 90 - the sum of all the pages of books allocated to student 1 is β12β, and student two is β34+ 67+ 90 = 191β, so the maximum is βmax(12, 191)= 191β.

12, 34 | 67, 90 - the sum of all the pages of books allocated to student 1 is β12+ 34 = 46β, and student two is β67+ 90 = 157β, so the maximum is βmax(46, 157)= 157β.

12, 34, 67 | 90 - the sum of all the pages of books allocated to student 1 is β12+ 34 +67 = 113β, and student two is β90β, so the maximum is βmax(113, 90)= 113β.

We are getting the minimum in the last case.

``````
Detailed explanation ( Input/output format, Notes, Images )
##### Sample Input 1:
``````4 2
12 34 67 90
``````
##### Sample Output 1:
``````113
``````
##### Explanation of sample input 1:
``````All possible ways to allocate the β4β books to '2' students are:

12 | 34, 67, 90 - the sum of all the pages of books allocated to student 1 is β12β, and student two is β34+ 67+ 90 = 191β, so the maximum is βmax(12, 191)= 191β.

12, 34 | 67, 90 - the sum of all the pages of books allocated to student 1 is β12+ 34 = 46β, and student two is β67+ 90 = 157β, so the maximum is βmax(46, 157)= 157β.

12, 34, 67 | 90 - the sum of all the pages of books allocated to student 1 is β12+ 34 +67 = 113β, and student two is β90β, so the maximum is βmax(113, 90)= 113β.

We are getting the minimum in the last case.

``````
##### Sample Input 2:
``````5 4
25 46 28 49 24
``````
##### Sample Output 2:
``````71
``````
##### Explanation of sample input 2:
``````All possible ways to allocate the β5β books to '4' students are:

25 | 46 | 28 | 49 24 - the sum of all the pages of books allocated to students 1, 2, 3, and 4 are '25', '46', '28', and '73'. So the maximum is '73'.

25 | 46 | 28 49 | 24 - the sum of all the pages of books allocated to students 1, 2, 3, and 4 are '25', '46', '77', and '24'. So the maximum is '77'.

25 | 46 28 | 49 | 24 - the sum of all the pages of books allocated to students 1, 2, 3, and 4 are '25', '74', '49', and '24'. So the maximum is '74'.

25 46 | 28 | 49 | 24 - the sum of all the pages of books allocated to students 1, 2, 3, and 4 are '71', '28', '49', and '24'. So the maximum is '71'.

We are getting the minimum in the last case.

``````
##### Expected time complexity:
``````The expected time complexity is O(n * log(s)), where βnβ is the number of integers in the array βarrβ and βsβ is the sum of all the elements of βarrβ.
``````
##### Constraints:
``````2 <= 'n' <= 10 ^ 3
1 <= 'm' <= 10 ^ 3
1 <= 'arr[i]' <= 10 ^ 9
The sum of all arr[i] does not exceed 10 ^ 9.

Where βnβ denotes the number of books and βmβ denotes the number of students. βarr[i]β denotes an element at position βiβ in the sequence.

Time limit: 1 second
``````
Console