Allocate Books
Given an array ‘arr’ of integer numbers . where ‘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 their students. Allocate books in such a way that:

1. Each student gets at least one book.

2. Each book should be allocated to a 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.

Example:

Let’s consider ‘n=4’ (number of books ) and ‘m=2’ (number of students).

‘arr = { 10, 20, 30, 40 }’.

All possible way to allocate the ‘4’ books in ‘2’ number of students is -

10 | 20, 30, 40 - sum of all the pages of books which allocated to student-1 is ‘10’, and student-2 is ‘20+ 30+ 40 = 90’ so maximum is ‘max(10, 90)= 90’.

10, 20 | 30, 40 - sum of all the pages of books which allocated to student-1 is ‘10+ 20 = 30’, and student-2 is ‘30+ 40 = 70’ so maximum is ‘max(30, 70)= 70’.

10, 20, 30 | 40 - sum of all the pages of books which allocated to student-1 is ‘10+ 20 +30 = 60’, and student-2 is ‘40’ so maximum is ‘max(60, 40)= 60’.

So possible maximum number of pages which allocated to a single student is { 90, 70, 60 }.

But you have to return a minimum of this so return ‘min(90,70,60) =60’.

Note:

1. Do not print anything, just return the maximum number of pages that are assigned to a student is minimum. 2. If it is not possible to assign the ‘n’ books to ‘m’ students then return ‘-1’.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The next ‘2*T’ lines represent the ‘T’ test cases. The first line of each test case contains two space-separated integers ‘n’ denoting the number of books and ‘m’ denotes the number of students. The second line of each test case contains ‘n’ space-separated integers denoting the number of pages in each of ‘n’ books.

Output Format

For each test case, return the minimum number of pages.

Constraints:

1

Question

Allocate Books

Given an array ‘arr’ of integer numbers . where ‘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 their students. Allocate books in such a way that:

1. Each student gets at least one book.

2. Each book should be allocated to a 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.

Example:

Let’s consider ‘n=4’ (number of books ) and ‘m=2’ (number of students).

‘arr = { 10, 20, 30, 40 }’.

subsequence

All possible way to allocate the ‘4’ books in ‘2’ number of students is -

10 | 20, 30, 40 - sum of all the pages of books which allocated to student-1 is ‘10’, and student-2 is ‘20+ 30+ 40 = 90’ so maximum is ‘max(10, 90)= 90’.

10, 20 | 30, 40 - sum of all the pages of books which allocated to student-1 is ‘10+ 20 = 30’, and student-2 is ‘30+ 40 = 70’ so maximum is ‘max(30, 70)= 70’.

10, 20, 30 | 40 - sum of all the pages of books which allocated to student-1 is ‘10+ 20 +30 = 60’, and student-2 is ‘40’ so maximum is ‘max(60, 40)= 60’.

So possible maximum number of pages which allocated to a single student is { 90, 70, 60 }.

But you have to return a minimum of this so return ‘min(90,70,60) =60’.

Note:

1. Do not print anything, just return the maximum number of pages that are assigned to a student is minimum.
2. If it is not possible to assign the ‘n’ books to ‘m’ students then return ‘-1’.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.

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

The second line of each test case contains ‘n’ space-separated integers denoting the number of pages in each of ‘n’ books.

Output Format

For each test case, return the minimum number of pages.

Constraints:

1 <= T <= 50
2 <= M <= N <= 10^3
1 <= A[i] <= 10^9
Sum of all A[i] do not more than 10^9.


Where ‘T’ is the total number of test cases, ‘N’ denotes the number of books and ‘M’ denotes the number of students. ‘A[i]’ denotes an element at position ‘i’ in the sequence.


Time limit: 1 second

Accepted Answer

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

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.

Space Complexity: O(1)Explanation:

O(1), we are using constant space.

Time Complexity: O(1)Explanation:

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

Accepted Answer

Binary Search

The basic idea is use ‘binary search’, we check each and every value, if ‘x’ can answer then we try to minimise it, else check another value.

Initially ‘min = 0’ and ‘max = sum of all pages’ and mid is ‘(max+min)/2’.
Check if it is possible to divide at least ‘mid’ number of pages in each student.
- If possible then check for some small value ‘(min+mid)/2’.
- Else check some greater value ‘(mid+ max)/2’.