Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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.

```
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.
Hence answer is β113β.
```

Detailed explanation

```
4 2
12 34 67 90
```

```
113
```

```
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.
Hence answer is β113β.
```

```
5 4
25 46 28 49 24
```

```
71
```

```
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.
Hence answer is β71β.
```

```
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β.
```

```
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
```