Allocate minimum number of pages | C ++ program for optimal allocation of pages ; Utility function to check if current minimum value is feasible or not . ; iterate over all books ; check if current number of pages are greater than curr_min that means we will get the result after mid no . of pages ; count how many students are required to distribute curr_min pages ; increment student count ; update curr_sum ; if students required becomes greater than given no . of students , return false ; else update curr_sum ; function to find minimum pages ; return - 1 if no . of books is less than no . of students ; Count total number of pages ; initialize start as 0 pages and end as total pages ; traverse until start <= end ; check if it is possible to distribute books by using mid as current minimum ; update result to current distribution as it 's the best we have found till now. ; as we are finding minimum and books are sorted so reduce end = mid - 1 that means ; if not possible means pages should be increased so update start = mid + 1 ; at - last return minimum no . of pages ; Drivers code ; Number of pages in books ; int m = 2 ; No . of students
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPossible ( int arr [ ] , int n , int m , int curr_min ) { int studentsRequired = 1 ; int curr_sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] > curr_min ) return false ; if ( curr_sum + arr [ i ] > curr_min ) { studentsRequired ++ ; curr_sum = arr [ i ] ; if ( studentsRequired > m ) return false ; } else curr_sum += arr [ i ] ; } return true ; } int findPages ( int arr [ ] , int n , int m ) { long long sum = 0 ; if ( n < m ) return -1 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; int start = 0 , end = sum ; int result = INT_MAX ; while ( start <= end ) { int mid = ( start + end ) / 2 ; if ( isPossible ( arr , n , m , mid ) ) { result = mid ; end = mid - 1 ; } else start = mid + 1 ; } return result ; } int main ( ) { int arr [ ] = { 12 , 34 , 67 , 90 } ; int n = sizeof arr / sizeof arr [ 0 ] ; cout << " Minimum ▁ number ▁ of ▁ pages ▁ = ▁ " << findPages ( arr , n , m ) << endl ; return 0 ; }