Allocate Minimum Pages Binary Search on Answer in DSA Java

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 pages limit and check if we can allocate books without exceeding it.

Analogy: Imagine dividing a pile of books among friends so that no one gets too heavy a load. You try a weight limit and see if everyone can carry their share without going over that limit.

Books: [100] -> [200] -> [300] -> [400] -> [500] -> null
Students: 3
Trying max pages limit: 500
Allocation example:
Student1: 100 -> 200 -> 300 (total 600 > 500, so no)
Student1: 100 -> 200 (total 300 ≤ 500)
Student2: 300 -> 400 (total 700 > 500, no)
Student2: 300 (total 300 ≤ 500)
Student3: 400 -> 500 (total 900 > 500, no)

Dry Run Walkthrough

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

Goal: Find the minimum maximum pages assigned to any student when books are allocated in order

Step 1: Set low to max book pages (500), high to sum of all pages (1500), start binary search

low=500, high=1500

Why: Minimum max pages can't be less than largest book, max can't be more than total pages

Step 2: Check mid = (500+1500)/2 = 1000, try allocation with max pages 1000

Try allocation with max_pages=1000

Why: Test if 1000 pages max per student is possible

Step 3: Allocate books: Student1 gets 100+200+300=600 ≤1000, Student2 gets 400 ≤1000, Student3 gets 500 ≤1000

Allocation possible with max_pages=1000

Why: All students can get books without exceeding 1000 pages

Step 4: Since allocation possible, try smaller max: high = mid = 1000

low=500, high=1000

Why: Try to find smaller max pages

Step 5: Check mid = (500+1000)/2 = 750, try allocation with max pages 750

Try allocation with max_pages=750

Why: Test if 750 pages max per student is possible

Step 6: Allocate books: Student1 gets 100+200+300=600 ≤750, Student2 gets 400 ≤750, Student3 gets 500 ≤750

Allocation possible with max_pages=750

Why: All students can get books without exceeding 750 pages

Step 7: Since allocation possible, try smaller max: high = mid = 750

low=500, high=750

Why: Try to find smaller max pages

Step 8: Check mid = (500+750)/2 = 625, try allocation with max pages 625

Try allocation with max_pages=625

Why: Test if 625 pages max per student is possible

Step 9: Allocate books: Student1 gets 100+200+300=600 ≤625, Student2 gets 400 ≤625, Student3 gets 500 ≤625

Allocation possible with max_pages=625

Why: All students can get books without exceeding 625 pages

Step 10: Since allocation possible, try smaller max: high = mid = 625

low=500, high=625

Why: Try to find smaller max pages

Step 11: Check mid = (500+625)/2 = 562, try allocation with max pages 562

Try allocation with max_pages=562

Why: Test if 562 pages max per student is possible

Step 12: Allocate books: Student1 gets 100+200=300 ≤562, Student2 gets 300+400=700 >562 (fail)

Allocation not possible with max_pages=562

Why: Second student exceeds max pages, allocation fails

Step 13: Since allocation failed, increase low: low = mid + 1 = 563

low=563, high=625

Why: Need larger max pages to allocate

Step 14: Check mid = (563+625)/2 = 594, try allocation with max pages 594

Try allocation with max_pages=594

Why: Test if 594 pages max per student is possible

Step 15: Allocate books: Student1 gets 100+200=300 ≤594, Student2 gets 300+400=700 >594 (fail)

Allocation not possible with max_pages=594

Why: Second student exceeds max pages, allocation fails

Step 16: Since allocation failed, increase low: low = mid + 1 = 595

low=595, high=625

Why: Need larger max pages to allocate

Step 17: Check mid = (595+625)/2 = 610, try allocation with max pages 610

Try allocation with max_pages=610

Why: Test if 610 pages max per student is possible

Step 18: Allocate books: Student1 gets 100+200+300=600 ≤610, Student2 gets 400 ≤610, Student3 gets 500 ≤610

Allocation possible with max_pages=610

Why: All students can get books without exceeding 610 pages

Step 19: Since allocation possible, try smaller max: high = mid = 610

low=595, high=610

Why: Try to find smaller max pages

Step 20: Check mid = (595+610)/2 = 602, try allocation with max pages 602

Try allocation with max_pages=602

Why: Test if 602 pages max per student is possible

Step 21: Allocate books: Student1 gets 100+200+300=600 ≤602, Student2 gets 400 ≤602, Student3 gets 500 ≤602

Allocation possible with max_pages=602

Why: All students can get books without exceeding 602 pages

Step 22: Since allocation possible, try smaller max: high = mid = 602

low=595, high=602

Why: Try to find smaller max pages

Step 23: Check mid = (595+602)/2 = 598, try allocation with max pages 598

Try allocation with max_pages=598

Why: Test if 598 pages max per student is possible

Step 24: Allocate books: Student1 gets 100+200=300 ≤598, Student2 gets 300+400=700 >598 (fail)

Allocation not possible with max_pages=598

Why: Second student exceeds max pages, allocation fails

Step 25: Since allocation failed, increase low: low = mid + 1 = 599

low=599, high=602

Why: Need larger max pages to allocate

Step 26: Check mid = (599+602)/2 = 600, try allocation with max pages 600

Try allocation with max_pages=600

Why: Test if 600 pages max per student is possible

Step 27: Allocate books: Student1 gets 100+200+300=600 ≤600, Student2 gets 400 ≤600, Student3 gets 500 ≤600

Allocation possible with max_pages=600

Why: All students can get books without exceeding 600 pages

Step 28: Since allocation possible, try smaller max: high = mid = 600

low=599, high=600

Why: Try to find smaller max pages

Step 29: Check mid = (599+600)/2 = 599, try allocation with max pages 599

Try allocation with max_pages=599

Why: Test if 599 pages max per student is possible

Step 30: Allocate books: Student1 gets 100+200=300 ≤599, Student2 gets 300+400=700 >599 (fail)

Allocation not possible with max_pages=599

Why: Second student exceeds max pages, allocation fails

Step 31: Since allocation failed, increase low: low = mid + 1 = 600

low=600, high=600

Why: Low meets high, search ends

Result:

Final allocation max pages = 600
Books allocated as:
Student1: 100 -> 200 -> 300 -> null
Student2: 400 -> null
Student3: 500 -> null

Annotated Code

DSA Java

public class AllocateMinimumPages {

    // Check if it is possible to allocate books such that max pages per student <= maxPages
    static boolean isPossible(int[] books, int students, int maxPages) {
        int requiredStudents = 1;
        int currentSum = 0;
        for (int pages : books) {
            if (pages > maxPages) return false; // single book exceeds maxPages
            if (currentSum + pages > maxPages) {
                requiredStudents++;
                currentSum = pages;
                if (requiredStudents > students) return false;
            } else {
                currentSum += pages;
            }
        }
        return true;
    }

    // Binary search to find minimum max pages
    static int findMinimumPages(int[] books, int students) {
        int low = 0;
        int high = 0;
        for (int pages : books) {
            if (pages > low) low = pages; // max single book pages
            high += pages; // sum of all pages
        }

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

    public static void main(String[] args) {
        int[] books = {100, 200, 300, 400, 500};
        int students = 3;
        int minPages = findMinimumPages(books, students);
        System.out.println("Minimum maximum pages allocated = " + minPages);
    }
}

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

Reject allocation if any single book is larger than maxPages

if (currentSum + pages > maxPages) { requiredStudents++; currentSum = pages; if (requiredStudents > students) return false; }

Start new student allocation if adding book exceeds maxPages; fail if too many students needed

for (int pages : books) { if (pages > low) low = pages; high += pages; }

Initialize binary search bounds: low=max single book, high=sum all pages

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

Binary search to find minimum max pages by testing feasibility

Output

Minimum maximum pages allocated = 600

Complexity Analysis

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

Space: O(1) because only variables for sums and counters are used, no extra data structures

vs Alternative: Naive approach tries all possible max pages from max book to sum, which is O(n * S), much slower than binary search

Edge Cases

Only one student

All books must be allocated to one student, so max pages is sum of all books

DSA Java

for (int pages : books) { if (pages > low) low = pages; high += pages; }

Number of students equals number of books

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

DSA Java

if (pages > maxPages) return false;

A book has more pages than allowed maxPages

Allocation fails immediately because no student can get that book

DSA Java

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 space combined with a feasibility check.

Common Mistakes

Mistake: Setting low to 0 instead of max single book pages
Fix: Initialize low to the maximum pages in any single book to avoid invalid allocations

Mistake: Not checking if a single book exceeds maxPages in feasibility
Fix: Add a check to immediately return false if any book is larger than maxPages

Mistake: Using high = max single book pages instead of sum of all pages
Fix: Set high to sum of all pages to cover the full search space

Summary

It finds the smallest maximum pages assigned to any student when allocating books in order.

Use it when you need to divide work or items fairly minimizing the maximum load.

The key is guessing a max limit and checking if allocation is possible, then narrowing the guess with binary search.

Practice

1. What is the main goal of the Allocate Minimum Pages problem using binary search on answer?

easy

A. To minimize the maximum number of pages assigned to a student

B. To maximize the total number of pages assigned

C. To find the average number of pages per student

D. To assign pages randomly among students

Solution

1. Step 1: Understand the problem objective

   The problem asks to allocate books to students so that the maximum pages assigned to any student is as small as possible.

2. Step 2: Identify the goal of binary search on answer

   Binary search is used to find the minimum possible maximum pages that can be assigned to a student.

3. Final Answer:

   To minimize the maximum number of pages assigned to a student -> Option A

4. Quick Check:

   Goal = minimize max pages [OK]

Hint: Focus on minimizing the largest pages assigned [OK]

Common Mistakes:

• Thinking the goal is to maximize pages
• Confusing average pages with maximum pages
• Assuming random allocation is acceptable

2. Which of the following is the correct way to initialize the binary search boundaries for the Allocate Minimum Pages problem in Java?

easy

A. int low = 0; int high = max pages in a single book;

B. int low = 0; int high = sum of all pages;

C. int low = max pages in a single book; int high = sum of all pages;

D. int low = sum of all pages; int high = max pages in a single book;

Solution

1. Step 1: Determine the minimum possible max pages

   The minimum max pages must be at least the largest single book's pages, because no book can be split.

2. Step 2: Determine the maximum possible max pages

   The maximum max pages is the sum of all pages if one student gets all books.

3. Final Answer:

   int low = max pages in a single book; int high = sum of all pages; -> Option C

4. Quick Check:

   low = max book pages, high = total pages [OK]

Hint: Low = max single book, High = sum all pages [OK]

Common Mistakes:

• Setting low to 0 which is invalid
• Swapping low and high values
• Using average pages as boundaries

3. Consider the books with pages [10, 20, 30, 40] and 2 students. What is the minimum maximum pages allocated to a student?

medium

A. 40

B. 70

C. 50

D. 60

Solution

1. Step 1: Check possible max pages allocations

   Try to split books so that max pages per student is minimized. Possible splits: [10,20,30] and [40] max=60; or [10,20] and [30,40] max=70.

2. Step 2: Choose minimum max pages

   Between 60 and 70, 60 is smaller and valid allocation.

3. Final Answer:

   60 -> Option D

4. Quick Check:

   Minimum max pages = 60 [OK]

Hint: Try splits and pick smallest max sum [OK]

Common Mistakes:

• Choosing sum of all pages as answer
• Ignoring largest single book pages
• Incorrectly splitting books

4. Given the following code snippet for checking feasibility in the Allocate Minimum Pages problem, what is the bug?

boolean isPossible(int[] pages, int students, int mid) {
    int count = 1, sum = 0;
    for (int page : pages) {
        sum += page;
        if (sum > mid) {
            count++;
            sum = 0;
        }
    }
    return count <= students;
}

medium

A. sum should be reset to current page, not zero, after count increment

B. count should be reset to zero inside the loop

C. The loop should start from index 1, not zero

D. The function should return count >= students

Solution

1. Step 1: Analyze sum reset logic

   When sum exceeds mid, count increments but sum resets to zero, losing the current page's value.

2. Step 2: Correct sum reset to current page

   Sum should reset to current page's value to include it in the new student's allocation.

3. Final Answer:

   sum should be reset to current page, not zero, after count increment -> Option A

4. Quick Check:

   Reset sum = current page [OK]

Hint: Reset sum to current page, not zero [OK]

Common Mistakes:

• Resetting sum to zero loses current page
• Returning wrong comparison for count and students
• Incorrect loop indexing

5. You have books with pages [12, 34, 67, 90] and 2 students. Using binary search on answer, what is the minimum maximum pages that can be allocated to a student? Show the reasoning.

hard

A. 90

B. 113

C. 101

D. 67

Solution

1. Step 1: Set binary search boundaries

   Low = max single book pages = 90, High = sum = 12+34+67+90=203.

2. Step 2: Check mid and feasibility

   Mid = (90+203)/2=146. Check if allocation possible with max 146 pages per student: [12,34,67] sum=113 <=146, next student gets [90]. Possible with 2 students.

3. Step 3: Narrow search

   Try lower mid: (90+146)/2=118. Check allocation: [12,34,67] sum=113 <=118, next student [90]. Possible.

4. Step 4: Try even lower mid

   Mid = (90+118)/2=104. Allocation: [12,34,67] sum=113 >104, so split: [12,34] sum=46 <=104, next student [67,90] sum=157 >104 not possible.

5. Step 5: Increase low to 105 and continue

   Mid = (105+118)/2=111. Allocation: [12,34,67] sum=113 >111 no, split: [12,34] sum=46 <=111, next student [67,90] sum=157 >111 no.

6. Step 6: Mid = (112+118)/2=115

   Allocation: [12,34,67] sum=113 <=115 yes, next student [90]. Possible.

7. Step 7: Narrow down to minimum feasible

   Try mid= (112+114)/2=113 allocation possible, mid=112 allocation not possible.

8. Final Answer:

   113 -> Option B

9. Quick Check:

   Minimum max pages = 113 [OK]

Hint: Use binary search between max book and total pages [OK]

Common Mistakes:

• Choosing max single book pages as answer
• Not checking feasibility correctly
• Stopping binary search too early