# Allocate Books || Binary Search

[Question]: Given an array 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.
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:

let booksArrayWithPages = [12, 34, 67, 90]
var booksCount = 4
var studentsCount = 2
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’.

``````// TC: O(Nlog(N))
// SC: O(1)
func bookAllocation(_ arr: [Int], _ booksCount: Int, _ studentsCount: Int) ->Int {
var start = 0
var sum = 0
for i in 0..<booksCount {
sum += arr[i]
}
var end = sum // end = sum of all array elements
var ans = -1    // initialize ans

var mid = start + (end-start)/2

while start<=end {
if isPossibleToBookAllocate(arr, booksCount, studentsCount, mid) {
//possible solution, save the ans and move to left to find minimal possilbe solution, coz right of this will also satisfy the condition
ans = mid
end = mid-1
} else {
//no soln exists, means more no. of students needed than given, so move to right to increase sum
//lower the search space, bring start infront
start = mid+1
}
mid = start+(end-start)/2
}
return ans
}

func isPossibleToBookAllocate(_ arr: [Int], _ booksCount: Int, _ studentCount: Int, _ mid: Int) -> Bool {
var currentStudentCount = 1
var pageSum = 0;    //min start with one student, and page sum=0, keep on adding value till it is<mid and rest give to other student and check
for i in 0..<booksCount {
if (pageSum + arr[i]) <= mid {
//a[i] current page sum value, maintain a running count
pageSum+=arr[i]    //save it || page sum represents the no. of pages alloted to the student in consideration right now
} else{
//allocate remaining pages to other student
currentStudentCount+=1
//check for no solution case
if currentStudentCount > studentCount || (arr[i] > mid){
return false;
//if student >m and the value of current is greater than mid, stop in these two cases
} else {
//we increases student count so new page sum value
//                 pageSum=0;
//                 pageSum+=arr[i];
//                 we can use above lines also for understanding, if starting from zero no needed for zero + in unary operator
pageSum = arr[i];
}
}
}
return true
}

let booksArrayWithPages = [12, 34, 67, 90]
var booksCount = 4
var studentsCount = 2
let minAllocatedBook = bookAllocation(booksArrayWithPages, booksCount, studentsCount)
print("Min allocation-- ", minAllocatedBook)// 113
``````