Allocate Minimum Pages

"""
We want to minimize the maximum number of pages assigned to any student.

Observations:
1. Each student must receive at least one book and books must be assigned contiguously.
2. The minimum possible value of the answer is max(arr),
   because the book with the maximum pages must be assigned to someone.
3. The maximum possible value of the answer is sum(arr),
   when a single student is assigned all the books.

So the answer lies in the range [max(arr), sum(arr)].

Binary Search on Answer:
We binary search on this range and assume a candidate value `x`
as the maximum pages allowed per student.

For a given `x`, we greedily assign books in order:
- Keep adding books to the current student until pages exceed `x`
- When exceeded, assign books to a new student

This allows us to compute the minimum number of students required
if no student is allowed more than `x` pages.

Decision:
- If required students <= k, the allocation is possible.
  Try to reduce `x` to find a better (smaller) maximum.
- If required students > k, `x` is too small and must be increased.

Trick:
Even if the allocation is possible, we continue shrinking the range
because we want the minimum possible maximum pages.

T.C:O(n log(sum(arr)))

Here we making the groups intensionally less than equal to the mid pages, not greater than k pages & the reason is suppose you finished grouping for any other algo, then some group will be having 5,3,1,9 so the answer is 9 so we are targeting to
force the mid on all the groups, make the groups less than or equal to 9.
"""

def minimum_count_of_students_with_n_pages(arr,max_pages): #it finds the total numbers of groups possible where the group combined pages is less than, equal to max_pages ie. mid
    students = 1
    cur = 0

    for pages in arr:
        if cur + pages <= max_pages:
            cur+=pages
        else:
            students += 1
            cur = pages

    return students

class Solution:
    def findPages(self, arr, k):
        if k>len(arr):
            return -1
        low,high=max(arr),sum(arr)
        while low<=high:
            mid= (low+high)//2 #check how many minimum students would be enough to get all the books where maximum pages allocated to a student doesn't cross the mid
            count=minimum_count_of_students_with_n_pages(arr,mid)

            if count<=k: #for < case, means the threshold is big so k groups couldn't form so we should reduce the threshold and for = case, we will check on the higher values, let's see we with more smaller values
                high=mid-1
            else:
                low=mid+1
        return low