Allocate Minimum Number of Pages Using Binary Search

Introduction

The Allocate Minimum Number of Pages problem is one of the most important DSA interview questions because it introduces a powerful idea called Binary Search on Answer.

In simple words, this problem asks you to distribute books among students in a fair way, so that the student who reads the most pages reads as little as possible.

This article explains the problem using simple, human language, real-life meaning, and a clear binary search–based solution that interviewers expect.

Real-World Meaning of Book Allocation

Imagine a school teacher who wants to distribute books among students:

• Each book has a certain number of pages

• Each student must get contiguous books

• The teacher wants to make sure no student is overloaded

The goal is to distribute books so that the maximum pages assigned to any student is minimum.

Problem Statement

You are given:

• An array where each element represents pages in a book

• An integer m representing number of students

Rules:

• Each student must get at least one book

• Books must be allocated contiguously

Your task is to minimize the maximum number of pages assigned to any student.

Example

Books:    [12, 34, 67, 90]
Students: 2

Output

Minimum maximum pages = 113

Explanation:

• Student 1 → [12, 34, 67] = 113 pages

• Student 2 → [90] = 90 pages

Before vs After Understanding

Brute Force Thinking (Before)

• Try all possible distributions

• Compare maximum pages

• Extremely slow and impractical

Binary Search Thinking (After)

• Search on the answer space

• Check if a distribution is possible

• Reduce search space step by step

Why Binary Search Works Here

Even though this is not a searching problem, binary search works because:

• The answer lies between a minimum and a maximum value

• If a distribution is possible for X pages, it will also be possible for any value greater than X

This monotonic behavior allows binary search.

What Interviewers Are Actually Testing

Interviewers want to see:

• Can you think beyond arrays and indexes?

• Do you understand binary search on answer?

• Can you convert real-world constraints into code?

This problem tests problem modeling skills.

Key Idea (Very Simple)

• The minimum possible answer is the largest single book

• The maximum possible answer is the sum of all pages

• Use binary search between these two values

Step-by-Step Logic

1. Set low = max number of pages in a book

2. Set high = sum of all pages

3. Find mid (possible answer)

4. Check if books can be allocated with mid as maximum pages

5. If possible, try smaller value (move left)

6. If not possible, try larger value (move right)

Feasibility Check (Very Important)

To check if allocation is possible:

• Assign books to students one by one

• If pages exceed mid, assign to next student

• If students required > m, allocation is not possible

Dry Run Example

Books: [12, 34, 67, 90], Students = 2

low	high	mid	possible?	move
90	203	146	yes	left
90	146	118	yes	left
90	118	104	no	right
105	118	111	no	right
112	118	115	yes	left
112	115	113	yes	left

Answer = 113

One-Line Logic Before Code

Use binary search on the answer and validate each guess.

Code Implementation (C++)

bool isPossible(vector<int>& books, int students, int maxPages) {
    int studentCount = 1;
    int pages = 0;

    for (int i = 0; i < books.size(); i++) {
        if (pages + books[i] <= maxPages) {
            pages += books[i];
        } else {
            studentCount++;
            pages = books[i];
            if (studentCount > students)
                return false;
        }
    }
    return true;
}

int allocateBooks(vector<int>& books, int students) {
    if (students > books.size()) return -1;

    int low = *max_element(books.begin(), books.end());
    int high = accumulate(books.begin(), books.end(), 0);
    int ans = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (isPossible(books, students, mid)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return ans;
}

Common Beginner Mistakes

• Trying all distributions

• Forgetting contiguous constraint

• Wrong low and high initialization

Time and Space Complexity

• Time Complexity: O(n log n)

• Space Complexity: O(1)

Easy Summary (Explain Like I’m 10)

If books are shared among students, we want no one to get too many pages. By guessing a maximum limit and checking if sharing is possible, we can keep reducing the limit until it becomes perfect. Binary search helps us guess smartly instead of randomly.

Summary

The Allocate Minimum Number of Pages problem is a classic example of binary search on answer. By identifying the valid search range and checking feasibility for each guessed value, you can efficiently minimize the maximum load on any student. This problem is frequently asked in interviews and is essential for mastering advanced binary search techniques in DSA.