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