Allocate Minimum Pages Binary Search on Answer in DSA C++

Mental Model

We want to split books among students so that the largest pages assigned to any student is as small as possible. We guess a maximum page limit and check if it works, then adjust the guess using binary search.

Analogy: Imagine you have a stack of books and a few friends. You want to give books to each friend so that no one has to read too many pages. You try a limit on pages per friend and see if you can distribute books without anyone crossing that limit. If yes, you try a smaller limit; if no, you try a bigger limit.

Books: [100] -> [200] -> [300] -> [400] -> null
Students: 3
Trying max pages per student: 400
Distribution:
Student1: 100 -> 200 (total 300)
Student2: 300 (total 300)
Student3: 400 (total 400)

Dry Run Walkthrough

Input: books pages: [100, 200, 300, 400], students: 3

Goal: Find the minimum maximum pages assigned to any student when books are divided in order among 3 students

Step 1: Set low to max book pages (400), high to sum of all pages (1000), mid = (400+1000)/2 = 700

low=400, mid=700, high=1000

Why: We start binary search between max single book and total pages

Step 2: Check if max pages 700 can allocate books to 3 students

Student1: 100 + 200 + 300 = 600 ≤ 700
Student2: 400 ≤ 700
Students used: 2 ≤ 3

Why: 700 is a valid max pages since only 2 students needed

Step 3: Since 700 works, try smaller max by setting high = mid = 700

low=400, high=700

Why: Try to find smaller max pages to minimize maximum

Step 4: Calculate new mid = (400+700)/2 = 550

low=400, mid=550, high=700

Why: Check feasibility with smaller max pages

Step 5: Check if max pages 550 can allocate books

Student1: 100 + 200 = 300 ≤ 550
Student2: 300 ≤ 550
Student3: 400 ≤ 550
Students used: 3 ≤ 3

Why: 550 is valid max pages with exactly 3 students

Step 6: Since 550 works, set high = mid = 550

low=400, high=550

Why: Try smaller max pages again

Step 7: Calculate new mid = (400+550)/2 = 475

low=400, mid=475, high=550

Why: Check feasibility with 475 max pages

Step 8: Check if max pages 475 can allocate books

Student1: 100 + 200 = 300 ≤ 475
Student2: 300 ≤ 475
Student3: 400 > 475 (needs new student)
Students used: 4 > 3 (not valid)

Why: 475 is too small, need more than 3 students

Step 9: Since 475 not valid, set low = mid + 1 = 476

low=476, high=550

Why: Increase minimum max pages

Step 10: Calculate new mid = (476+550)/2 = 513

low=476, mid=513, high=550

Why: Check feasibility with 513 max pages

Step 11: Check if max pages 513 can allocate books

Student1: 100 + 200 = 300 ≤ 513
Student2: 300 ≤ 513
Student3: 400 ≤ 513
Students used: 3 ≤ 3 (valid)

Why: 513 works with 3 students

Step 12: Since 513 works, set high = mid = 513

low=476, high=513

Why: Try smaller max pages

Step 13: Calculate new mid = (476+513)/2 = 494

low=476, mid=494, high=513

Why: Check feasibility with 494 max pages

Step 14: Check if max pages 494 can allocate books

Student1: 100 + 200 = 300 ≤ 494
Student2: 300 ≤ 494
Student3: 400 > 494 (needs new student)
Students used: 4 > 3 (not valid)

Why: 494 too small, need more students

Step 15: Since 494 not valid, set low = mid + 1 = 495

low=495, high=513

Why: Increase minimum max pages

Step 16: Calculate new mid = (495+513)/2 = 504

low=495, mid=504, high=513

Why: Check feasibility with 504 max pages

Step 17: Check if max pages 504 can allocate books

Student1: 100 + 200 = 300 ≤ 504
Student2: 300 ≤ 504
Student3: 400 ≤ 504
Students used: 3 ≤ 3 (valid)

Why: 504 works with 3 students

Step 18: Since 504 works, set high = mid = 504

low=495, high=504

Why: Try smaller max pages

Step 19: Calculate new mid = (495+504)/2 = 499

low=495, mid=499, high=504

Why: Check feasibility with 499 max pages

Step 20: Check if max pages 499 can allocate books

Student1: 100 + 200 = 300 ≤ 499
Student2: 300 ≤ 499
Student3: 400 > 499 (needs new student)
Students used: 4 > 3 (not valid)

Why: 499 too small

Step 21: Since 499 not valid, set low = mid + 1 = 500

low=500, high=504

Why: Increase minimum max pages

Step 22: Calculate new mid = (500+504)/2 = 502

low=500, mid=502, high=504

Why: Check feasibility with 502 max pages

Step 23: Check if max pages 502 can allocate books

Student1: 100 + 200 = 300 ≤ 502
Student2: 300 ≤ 502
Student3: 400 ≤ 502
Students used: 3 ≤ 3 (valid)

Why: 502 works

Step 24: Since 502 works, set high = mid = 502

low=500, high=502

Why: Try smaller max pages

Step 25: Calculate new mid = (500+502)/2 = 501

low=500, mid=501, high=502

Why: Check feasibility with 501 max pages

Step 26: Check if max pages 501 can allocate books

Student1: 100 + 200 = 300 ≤ 501
Student2: 300 ≤ 501
Student3: 400 > 501 (needs new student)
Students used: 4 > 3 (not valid)

Why: 501 too small

Step 27: Since 501 not valid, set low = mid + 1 = 502

low=502, high=502

Why: low meets high, search ends

Result:

Final minimum max pages = 502
Books distributed as:
Student1: 100 + 200 = 300
Student2: 300
Student3: 400

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

bool canAllocate(const vector<int>& books, int students, int maxPages) {
    int requiredStudents = 1;
    int currentSum = 0;
    for (int pages : books) {
        if (pages > maxPages) return false; // single book too big
        if (currentSum + pages > maxPages) {
            requiredStudents++;
            currentSum = pages; // start new student
        } else {
            currentSum += pages; // add book to current student
        }
    }
    return requiredStudents <= students;
}

int allocateMinimumPages(const vector<int>& books, int students) {
    int low = *max_element(books.begin(), books.end());
    int high = accumulate(books.begin(), books.end(), 0);
    int result = high;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canAllocate(books, students, mid)) {
            result = mid; // mid works, try smaller
            high = mid - 1;
        } else {
            low = mid + 1; // mid too small
        }
    }
    return result;
}

int main() {
    vector<int> books = {100, 200, 300, 400};
    int students = 3;
    int minPages = allocateMinimumPages(books, students);
    cout << minPages << endl;
    return 0;
}

if (pages > maxPages) return false; // single book too big

Check if any single book exceeds max pages limit, making allocation impossible

if (currentSum + pages > maxPages) { requiredStudents++; currentSum = pages; } else { currentSum += pages; }

Assign books to current student until maxPages exceeded, then allocate to next student

while (low <= high) { int mid = low + (high - low) / 2; if (canAllocate(...)) { result = mid; high = mid - 1; } else { low = mid + 1; } }

Binary search to find minimum max pages that can allocate all books to students

Output

502

Complexity Analysis

Time: O(n log m) where n is number of books and m is sum of pages, because binary search runs log m times and each feasibility check scans all books once

Space: O(n) for storing books array

vs Alternative: Naive approach tries all possible max pages from max book to sum, which is O(n*m) and too slow; binary search reduces it to O(n log m)

Edge Cases

Only one student

All books must be assigned to one student, so result is sum of all pages

DSA C++

int low = *max_element(books.begin(), books.end());

Number of students equals number of books

Each student gets exactly one book, so result is max pages of any single book

DSA C++

if (pages > maxPages) return false;

A book has more pages than any guessed maxPages

Allocation fails immediately, binary search adjusts

DSA C++

if (pages > maxPages) return false;

When to Use This Pattern

When asked to split an array into subarrays minimizing the maximum sum, use binary search on the answer to efficiently find the optimal maximum sum.

Common Mistakes

Mistake: Not checking if a single book exceeds the current maxPages guess, causing incorrect feasibility results
Fix: Add a check to return false immediately if any book has pages greater than maxPages

Mistake: Updating low and high incorrectly in binary search, causing infinite loops or wrong answers
Fix: Use low = mid + 1 when mid is invalid, and high = mid - 1 when mid is valid

Summary

It finds the smallest maximum number of pages assigned to any student when dividing books in order.

Use it when you need to split an array into contiguous parts minimizing the largest sum among parts.

The key insight is to guess a maximum limit and check feasibility, then narrow down the guess using binary search.