Allocate Minimum Pages Binary Search on Answer in DSA C#

Mental Model

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

Analogy: Imagine dividing a stack of books among friends so that no one carries too many pages. You try a weight limit and see if everyone can carry their share without exceeding it. If yes, you try a smaller limit; if no, you try a bigger one.

Books: [100] -> [200] -> [300] -> [400] -> [500] -> null
Students: 3
Goal: Minimize max pages per student

Dry Run Walkthrough

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

Goal: Find the smallest maximum pages any student has to read when books are divided 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 to allocate books with max 1000 pages per student

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 pages, Student2 gets 400 pages, Student3 gets 500 pages

Allocation: [100,200,300] -> Student1 (600 pages)
[400] -> Student2 (400 pages)
[500] -> Student3 (500 pages)

Why: All students have pages ≤ 1000, allocation possible

Step 4: Since allocation possible, try smaller max: high = mid - 1 = 999

low=500, high=999

Why: Try to find smaller max pages per student

Step 5: Check mid = (500+999)/2 = 749; try allocation with max 749 pages

Try allocation with max_pages=749

Why: Test if 749 pages max per student is possible

Step 6: Allocate books: Student1 gets 100+200+300=600 pages, Student2 gets 400 pages (exceeds 749?), no, 400 ≤ 749, Student3 gets 500 pages

Allocation: [100,200,300] -> Student1 (600 pages)
[400] -> Student2 (400 pages)
[500] -> Student3 (500 pages)

Why: All students have pages ≤ 749, allocation possible

Step 7: Try smaller max: high = mid - 1 = 748

low=500, high=748

Why: Try to reduce max pages further

Step 8: Check mid = (500+748)/2 = 624; try allocation with max 624 pages

Try allocation with max_pages=624

Why: Test if 624 pages max per student is possible

Step 9: Allocate books: Student1 gets 100+200+300=600 pages, Student2 gets 400 pages (exceeds 624?), no, 400 ≤ 624, Student3 gets 500 pages

Allocation: [100,200,300] -> Student1 (600 pages)
[400] -> Student2 (400 pages)
[500] -> Student3 (500 pages)

Why: All students have pages ≤ 624, allocation possible

Step 10: Try smaller max: high = mid - 1 = 623

low=500, high=623

Why: Try to reduce max pages further

Step 11: Check mid = (500+623)/2 = 561; try allocation with max 561 pages

Try allocation with max_pages=561

Why: Test if 561 pages max per student is possible

Step 12: Allocate books: Student1 gets 100+200=300 pages, Student2 gets 300+400=700 pages (exceeds 561?), yes, allocation fails

Allocation fails at Student2 with 700 pages > 561

Why: Max pages too small, allocation not possible

Step 13: Increase low: low = mid + 1 = 562

low=562, high=623

Why: Try larger max pages to allow allocation

Step 14: Check mid = (562+623)/2 = 592; try allocation with max 592 pages

Try allocation with max_pages=592

Why: Test if 592 pages max per student is possible

Step 15: Allocate books: Student1 gets 100+200=300 pages, Student2 gets 300+400=700 pages (exceeds 592?), yes, allocation fails

Allocation fails at Student2 with 700 pages > 592

Why: Max pages too small, allocation not possible

Step 16: Increase low: low = mid + 1 = 593

low=593, high=623

Why: Try larger max pages to allow allocation

Step 17: Check mid = (593+623)/2 = 608; try allocation with max 608 pages

Try allocation with max_pages=608

Why: Test if 608 pages max per student is possible

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

Allocation: [100,200,300] -> Student1 (600 pages)
[400] -> Student2 (400 pages)
[500] -> Student3 (500 pages)

Why: Allocation possible with max 608 pages

Step 19: Try smaller max: high = mid - 1 = 607

low=593, high=607

Why: Try to reduce max pages further

Step 20: Check mid = (593+607)/2 = 600; try allocation with max 600 pages

Try allocation with max_pages=600

Why: Test if 600 pages max per student is possible

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

Allocation: [100,200,300] -> Student1 (600 pages)
[400] -> Student2 (400 pages)
[500] -> Student3 (500 pages)

Why: Allocation possible with max 600 pages

Step 22: Try smaller max: high = mid - 1 = 599

low=593, high=599

Why: Try to reduce max pages further

Step 23: Check mid = (593+599)/2 = 596; try allocation with max 596 pages

Try allocation with max_pages=596

Why: Test if 596 pages max per student is possible

Step 24: Allocate books: Student1 gets 100+200=300 pages, Student2 gets 300+400=700 pages (exceeds 596?), yes, allocation fails

Allocation fails at Student2 with 700 pages > 596

Why: Max pages too small, allocation not possible

Step 25: Increase low: low = mid + 1 = 597

low=597, high=599

Why: Try larger max pages to allow allocation

Step 26: Check mid = (597+599)/2 = 598; try allocation with max 598 pages

Try allocation with max_pages=598

Why: Test if 598 pages max per student is possible

Step 27: Allocate books: Student1 gets 100+200=300 pages, Student2 gets 300+400=700 pages (exceeds 598?), yes, allocation fails

Allocation fails at Student2 with 700 pages > 598

Why: Max pages too small, allocation not possible

Step 28: Increase low: low = mid + 1 = 599

low=599, high=599

Why: Try larger max pages to allow allocation

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

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 pages, Student2 gets 300+400=700 pages (exceeds 599?), yes, allocation fails

Allocation fails at Student2 with 700 pages > 599

Why: Max pages too small, allocation not possible

Step 31: Increase low: low = mid + 1 = 600

low=600, high=599

Why: low > high means search ends

Result:

Final minimum max pages per student = 600
Allocation: [100,200,300] -> Student1 (600 pages)
[400] -> Student2 (400 pages)
[500] -> Student3 (500 pages)

Annotated Code

DSA C#

using System;

class AllocateMinimumPages
{
    // Check if books can be allocated to students with maxPages limit
    static bool IsPossible(int[] books, int students, int maxPages)
    {
        int requiredStudents = 1;
        int currentSum = 0;
        foreach (int pages in 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 AllocatePages(int[] books, int students)
    {
        int low = 0;
        int high = 0;
        foreach (int pages in books) high += pages;
        low = 0;
        foreach (int pages in books) if (pages > low) low = 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; // try bigger max
            }
        }
        return result;
    }

    static void Main()
    {
        int[] books = {100, 200, 300, 400, 500};
        int students = 3;
        int minMaxPages = AllocatePages(books, students);
        Console.WriteLine(minMaxPages);
    }
}

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

guard against impossible allocation if a single book is larger than maxPages

if (currentSum + pages > maxPages)

if adding current book exceeds maxPages, allocate to next student

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

increment student count and check if allocation exceeds available students

int low = 0; int high = 0; foreach (int pages in books) high += pages; low = 0; foreach (int pages in books) if (pages > low) low = pages;

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

while (low <= high)

binary search loop to find minimum max pages

int mid = low + (high - low) / 2;

calculate mid as candidate max pages

if (IsPossible(books, students, mid)) { result = mid; high = mid - 1; // try smaller max }

if allocation possible with mid, try smaller max

else { low = mid + 1; // try bigger max }

if allocation not possible, try bigger max

Output

600

Complexity Analysis

Time: O(n log m) where n is number of books and m is sum of pages; binary search runs log m times and each check is O(n)

Space: O(1) because allocation check uses constant extra space

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

Edge Cases

Single book larger than any max pages guess

Allocation immediately fails because no student can read that book alone

DSA C#

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

Number of students equals number of books

Minimum max pages is max pages of any single book

DSA C#

low = max single book pages initialization

Only one student

Minimum max pages is sum of all pages (all books to one student)

DSA C#

high = sum of all pages initialization

When to Use This Pattern

When asked to split an array into subarrays minimizing the maximum sum, use binary search on the answer space because direct search is too slow.

Common Mistakes

Mistake: Not setting low to max single book pages, causing invalid guesses
Fix: Initialize low as the maximum pages in any single book before binary search

Mistake: Not checking if a single book exceeds maxPages in allocation check
Fix: Add guard to return false if any book pages > maxPages

Summary

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

Use it when you need to split workloads fairly minimizing the maximum load.

The key insight is to binary search the answer space and check feasibility efficiently.

Practice

1. What is the main goal of the Allocate Minimum Pages problem when using binary search on the 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 to students

Solution

1. Step 1: Understand the problem goal

   The problem wants to split book pages among students so that the student with the most pages has as few pages as possible.

2. Step 2: Identify the binary search target

   Binary search is used to find the minimum possible maximum pages assigned to any 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 any student gets [OK]

Common Mistakes:

• Thinking it maximizes total pages
• Confusing average with maximum
• Assuming random assignment

2. Which of the following is the correct way to initialize the binary search range for the minimum pages problem in C#?

easy

A. int low = 0, high = pages.Max();

B. int low = 0, high = pages.Sum();

C. int low = pages.Max(), high = pages.Sum();

D. int low = pages.Sum(), high = pages.Max();

Solution

1. Step 1: Determine the minimum and maximum possible pages

   The minimum max pages must be at least the largest single book (pages.Max()), and the maximum is the sum of all pages (pages.Sum()).

2. Step 2: Set binary search range accordingly

   Set low = pages.Max() and high = pages.Sum() to cover all possible max page values.

3. Final Answer:

   int low = pages.Max(), high = pages.Sum(); -> Option C

4. Quick Check:

   low = max page, high = sum pages [OK]

Hint: Low starts at max single book, high at total pages [OK]

Common Mistakes:

• Starting low at 0 (too low)
• Swapping low and high
• Using max as low and max as high

3. Given the array pages = [10, 20, 30, 40] and students = 2, what is the minimum maximum pages assigned after running the binary search solution?

medium

A. 70

B. 50

C. 40

D. 60

Solution

1. Step 1: Understand the problem with given input

   We want to split [10,20,30,40] into 2 students minimizing the max pages assigned.

2. Step 2: Check possible splits and their max pages

   Possible splits: [10,20,30] & [40] max=60; [10,20] & [30,40] max=70; [10] & [20,30,40] max=90; [10,20,30,40] & [] invalid. The minimum max is 60 or 50? Actually, [10,20,30] & [40] max=60, but [10,20] & [30,40] max=70. Check if 50 is possible: [10,20] & [30,40] max=70 >50 no; [10,20,30] & [40] max=60 >50 no; So 50 is not possible. But 60 is possible. So minimum max pages is 60.

3. Final Answer:

   60 -> Option D

4. Quick Check:

   Minimum max pages = 60 [OK]

Hint: Try splitting pages to minimize largest sum per student [OK]

Common Mistakes:

• Choosing max single book (40) as answer
• Choosing total sum (100) as answer
• Not checking all splits

4. Consider this C# code snippet for checking feasibility in the minimum pages problem:

bool IsPossible(int[] pages, int students, int mid) {
    int count = 1, sum = 0;
    foreach (int page in pages) {
        if (sum + page > mid) {
            count++;
            sum = page;
        } else {
            sum += page;
        }
    }
    return count <= students;
}

What is the bug in this code?

medium

A. It should return count >= students instead of count <= students

B. It does not handle the case when a single book has more pages than mid

C. It increments count incorrectly inside the loop

D. It resets sum to zero instead of page after incrementing count

Solution

1. Step 1: Analyze the feasibility check logic

   The function checks if pages can be allocated so no student gets more than mid pages.

2. Step 2: Identify missing check for single book pages

   If any single book has pages > mid, allocation is impossible, but code does not check this, causing wrong results.

3. Final Answer:

   It does not handle the case when a single book has more pages than mid -> Option B

4. Quick Check:

   Check single book > mid to avoid wrong feasibility [OK]

Hint: Always check if any single book exceeds mid [OK]

Common Mistakes:

• Ignoring single book size check
• Wrong comparison operator in return
• Resetting sum incorrectly

5. You have pages = [12, 34, 67, 90] and students = 2. Using binary search on answer, what is the minimum maximum pages that can be allocated? Also, explain why the answer is not the maximum single book pages.

hard

A. 113, because splitting as [12,34,67] and [90] minimizes max pages

B. 90, because the largest single book sets the minimum max pages

C. 67, because the average pages per student is less than 70

D. 123, because total pages must be divided equally

Solution

1. Step 1: Calculate total and max pages

   Total pages = 12+34+67+90 = 203; max single book = 90.

2. Step 2: Check possible splits for 2 students

   Splits: [12,34,67] & [90] max=113; [12,34] & [67,90] max=157; [12] & [34,67,90] max=191. Minimum max pages is 113.

3. Step 3: Explain why answer is not max single book

   Because 90 alone is too small to cover all pages in 2 students without exceeding max pages, the minimum max pages must be higher than 90.

4. Final Answer:

   113, because splitting as [12,34,67] and [90] minimizes max pages -> Option A

5. Quick Check:

   Minimum max pages = 113 > max single book 90 [OK]

Hint: Check splits; answer ≥ max single book, often higher [OK]

Common Mistakes:

• Choosing max single book as answer
• Ignoring total pages sum
• Assuming equal division always works