Lecture 15: Book Allocation Problem

[ishansurdi]

1. Problem: When the current student's page sum exceeded mid, the code incorrectly added the book's pages to pagesum instead of starting a new student's allocation.
   Impact: Incorrect allocation logic caused feasibility checks to fail.
   Binary Search Midpoint Calculation:

2. Problem: mid was calculated as sum + (end - sum) / 2, which used the wrong boundaries (sum instead of start).
   Impact: Binary search did not narrow down the range correctly.
   No Edge Case Handling (m > n):

3. Problem: The code didn't check if the number of students (m) was greater than the number of books (n).
   Impact: Returned incorrect results when allocation was impossible.
   Incorrect Return Value:

4. Problem: The function always returned -1 due to misplaced logic.
   Impact: Even valid allocations failed to return the correct result.

[shubham4672]

int findPages(vector<int>& arr, int n, int m) { if(m>n){ // add this return -1; } int sum = 0; for(int i = 0; i < n; i++){ sum += arr[i]; } int start = 0, end = sum; int ans = -1; while(start <= end){ int mid = start + (end - start) / 2; if(isPossible(arr, n, m, mid)){ ans = mid; end = mid - 1; } else{ start = mid + 1; } } return ans; }
Hope this is great and to optimize more start with the maximum element in the array. Which ensures we never assign fewer pages than the biggest book. TC: O(log(sum-max))