Allocate Books

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

The first line contains two space-separated integers ‘n’ denoting the number of books and ‘m’ denotes the number of students. The second line contains ‘n’ space-separated integers denoting the number of pages in each of ‘n’ books.

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

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

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

Linear Search

The basic idea is that, try each and every possible value that can be answered. It can be from ‘1’ to the sum of ‘arr’.

Find the sum of all the elements of ‘arr’ in a variable ‘sum’.
Iterate a loop ‘i’ from ‘1’ to ‘sum’(inclusive).
Check for every ‘i’, if it is possible to divide the at least ‘i’ pages to every student.
- If possible then return ‘i’ because we are iterating from minimum then it is the minimum answer.
- Else check for ‘i+1’.
If the number of ‘n<m’ then return ‘-1’, because the number of students is more than the number of books.

How to check - if it is possible to divide at least ‘mid’ number of pages in each student

Iterate a loop ‘i’, if sum of some contiguous books pages is less than or equals to mid then assign this sou to a single student and check for remain student and at the end if is possible then can say it is possible that ‘mid’ number of pages is possible to assign ‘m’ student.

Time Complexity

O(n * s), where ‘n’ is the number of integers in the array ‘arr’ and ‘s’ is the sum of all the elements of ‘arr’.

We are using two nested loops of size ‘s’ and ‘n’.

Therefore the time complexity is O(n * s).

Space Complexity

O(1)

We are using constant space.

Therefore the space complexity is O(1).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of sample input 1:

Sample Input 2:

Sample Output 2:

Explanation of sample input 2:

Expected time complexity:

Constraints:

How to check - if it is possible to divide at least ‘mid’ number of pages in each student