23. Allocate Minimum Pages
✅ GFG solution to the Allocate Minimum Pages problem: find optimal book allocation to minimize maximum pages per student using binary search technique. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given an array arr[] of integers, where each element arr[i] represents the number of pages in the i-th book. You also have an integer k representing the number of students. The task is to allocate books to each student such that:
Each student receives at least one book.
Each student is assigned a contiguous sequence of books.
No book is assigned to more than one student.
The objective is to minimize the maximum number of pages assigned to any student. In other words, out of all possible allocations, find the arrangement where the student who receives the most pages still has the smallest possible maximum.
Note: If it is not possible to allocate books to all students, return -1.
📘 Examples
Example 1
Input: arr[] = [12, 34, 67, 90], k = 2
Output: 113
Explanation: Allocation can be done in following ways:
=> [12] and [34, 67, 90] Maximum Pages = 191
=> [12, 34] and [67, 90] Maximum Pages = 157
=> [12, 34, 67] and [90] Maximum Pages = 113.
The third combination has the minimum pages assigned to a student which is 113.Example 2
Input: arr[] = [15, 17, 20], k = 5
Output: -1
Explanation: Since there are more students than total books, it's impossible to allocate a book to each student.🔒 Constraints
$1 \le \text{arr.size()} \le 10^6$
$1 \le \text{arr}[i], k \le 10^3$
✅ My Approach
The optimal approach uses Binary Search on the answer space to efficiently find the minimum possible maximum pages allocation:
Binary Search on Answer
Define Search Space:
Lower bound: Maximum element in array (minimum possible answer - at least one student must get the largest book)
Upper bound: Sum of all elements (maximum possible answer - one student gets all books)
Binary Search Logic:
For each mid value, check if it's possible to allocate books to
kstudents such that no student gets more thanmidpagesIf possible, search for smaller values (move right boundary to mid)
If not possible, search for larger values (move left boundary to mid + 1)
Feasibility Check:
Use greedy approach: assign books to current student until adding next book exceeds
midWhen limit exceeded, assign remaining books to next student
If total students needed ≤ k, allocation is feasible
Edge Case:
If k > number of books, return -1 (impossible to give each student at least one book)
Algorithm Steps:
Check if k > n, return -1
Set left = max(arr), right = sum(arr)
While left < right:
Calculate mid = left + (right - left) / 2
Check if allocation with max pages = mid is feasible
If feasible: right = mid (try for smaller maximum)
If not feasible: left = mid + 1 (need larger maximum)
Return left (minimum possible maximum pages)
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n × log(sum)), where n is the number of books and sum is the total pages. The binary search runs in O(log(sum)) iterations, and each feasibility check takes O(n) time.
Expected Auxiliary Space Complexity: O(1), as we only use a constant amount of additional space for variables regardless of input size.
⚡ Code (C)
int findPages(int arr[], int n, int k) {
if (k > n) return -1;
int l = arr[0], r = 0;
for (int i = 0; i < n; i++) {
if (arr[i] > l) l = arr[i];
r += arr[i];
}
while (l < r) {
int m = l + (r - l) / 2;
int s = 1, p = 0;
for (int i = 0; i < n; i++) {
if (p + arr[i] > m) { s++; p = arr[i]; }
else p += arr[i];
}
s <= k ? (r = m) : (l = m + 1);
}
return l;
}🧑💻 Code (C++)
class Solution {
public:
int findPages(vector<int> &arr, int k) {
if (k > arr.size()) return -1;
int l = *max_element(arr.begin(), arr.end());
int r = accumulate(arr.begin(), arr.end(), 0);
while (l < r) {
int m = l + (r - l) / 2;
int s = 1, p = 0;
for (int x : arr) {
if (p + x > m) { s++; p = x; }
else p += x;
}
s <= k ? r = m : l = m + 1;
}
return l;
}
};☕ Code (Java)
class Solution {
public int findPages(int[] arr, int k) {
if (k > arr.length) return -1;
int l = arr[0], r = 0;
for (int x : arr) {
l = Math.max(l, x);
r += x;
}
while (l < r) {
int m = l + (r - l) / 2;
int s = 1, p = 0;
for (int x : arr) {
if (p + x > m) { s++; p = x; }
else p += x;
}
if (s <= k) r = m;
else l = m + 1;
}
return l;
}
}🐍 Code (Python)
class Solution:
def findPages(self, arr, k):
if k > len(arr): return -1
l, r = max(arr), sum(arr)
while l < r:
m = (l + r) // 2
s, p = 1, 0
for x in arr:
if p + x > m: s, p = s + 1, x
else: p += x
r, l = (m, l) if s <= k else (r, m + 1)
return l🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated