Allocate Minimum Pages Binary Search on Answer in DSA Python

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 within that limit.

Analogy: Imagine you have a pile of books and a few friends. You want to give books to each friend so that no one gets too many pages. You try a guess for the max pages a friend can get, then see if you can hand out all books without breaking that guess.

Books: [100] -> [200] -> [300] -> [400] -> [500]
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 assigned to any student when books are divided among 3 students

Step 1: Set low = max book pages = 500, high = sum of all pages = 1500

low=500, high=1500

Why: Minimum max pages can't be less than largest book; maximum is sum of all pages

Step 2: Calculate mid = (500 + 1500) // 2 = 1000; check if allocation possible with max 1000 pages

Trying max_pages=1000

Why: Mid is our guess for max pages per student

Step 3: Allocate books: Student 1 gets 100+200+300=600 pages, Student 2 gets 400 pages, Student 3 gets 500 pages

Allocation possible with max_pages=1000

Why: All books allocated within max_pages=1000

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

low=500, high=999

Why: Try to find smaller max pages

Step 5: Calculate mid = (500 + 999) // 2 = 749; check allocation with max 749

Trying max_pages=749

Why: New guess for max pages

Step 6: Allocate books: Student 1 gets 100+200=300 pages, Student 2 gets 300 pages, Student 3 gets 400+500=900 pages (exceeds 749)

Allocation not possible with max_pages=749

Why: Last student exceeds max_pages, allocation fails

Step 7: Since allocation failed, increase low: low = mid + 1 = 750

low=750, high=999

Why: Need larger max pages to allocate

Step 8: Calculate mid = (750 + 999) // 2 = 874; check allocation with max 874

Trying max_pages=874

Why: New guess for max pages

Step 9: Allocate books: Student 1 gets 100+200+300=600 pages, Student 2 gets 400 pages, Student 3 gets 500 pages

Allocation possible with max_pages=874

Why: All books allocated within max_pages=874

Step 10: Since allocation possible, try smaller max: high = mid - 1 = 873

low=750, high=873

Why: Try to find smaller max pages

Step 11: Calculate mid = (750 + 873) // 2 = 811; check allocation with max 811

Trying max_pages=811

Why: New guess for max pages

Step 12: Allocate books: Student 1 gets 100+200+300=600 pages, Student 2 gets 400 pages, Student 3 gets 500 pages

Allocation possible with max_pages=811

Why: All books allocated within max_pages=811

Step 13: Since allocation possible, try smaller max: high = mid - 1 = 810

low=750, high=810

Why: Try to find smaller max pages

Step 14: Calculate mid = (750 + 810) // 2 = 780; check allocation with max 780

Trying max_pages=780

Why: New guess for max pages

Step 15: Allocate books: Student 1 gets 100+200+300=600 pages, Student 2 gets 400 pages, Student 3 gets 500 pages

Allocation possible with max_pages=780

Why: All books allocated within max_pages=780

Step 16: Since allocation possible, try smaller max: high = mid - 1 = 779

low=750, high=779

Why: Try to find smaller max pages

Step 17: Calculate mid = (750 + 779) // 2 = 764; check allocation with max 764

Trying max_pages=764

Why: New guess for max pages

Step 18: Allocate books: Student 1 gets 100+200+300=600 pages, Student 2 gets 400 pages, Student 3 gets 500 pages

Allocation possible with max_pages=764

Why: All books allocated within max_pages=764

Step 19: Since allocation possible, try smaller max: high = mid - 1 = 763

low=750, high=763

Why: Try to find smaller max pages

Step 20: Calculate mid = (750 + 763) // 2 = 756; check allocation with max 756

Trying max_pages=756

Why: New guess for max pages

Step 21: Allocate books: Student 1 gets 100+200=300 pages, Student 2 gets 300 pages, Student 3 gets 400+500=900 pages (exceeds 756)

Allocation not possible with max_pages=756

Why: Last student exceeds max_pages, allocation fails

Step 22: Since allocation failed, increase low: low = mid + 1 = 757

low=757, high=763

Why: Need larger max pages to allocate

Step 23: Calculate mid = (757 + 763) // 2 = 760; check allocation with max 760

Trying max_pages=760

Why: New guess for max pages

Step 24: Allocate books: Student 1 gets 100+200+300=600 pages, Student 2 gets 400 pages, Student 3 gets 500 pages

Allocation possible with max_pages=760

Why: All books allocated within max_pages=760

Step 25: Since allocation possible, try smaller max: high = mid - 1 = 759

low=757, high=759

Why: Try to find smaller max pages

Step 26: Calculate mid = (757 + 759) // 2 = 758; check allocation with max 758

Trying max_pages=758

Why: New guess for max pages

Step 27: Allocate books: Student 1 gets 100+200=300 pages, Student 2 gets 300 pages, Student 3 gets 400+500=900 pages (exceeds 758)

Allocation not possible with max_pages=758

Why: Last student exceeds max_pages, allocation fails

Step 28: Since allocation failed, increase low: low = mid + 1 = 759

low=759, high=759

Why: Need larger max pages to allocate

Step 29: Calculate mid = (759 + 759) // 2 = 759; check allocation with max 759

Trying max_pages=759

Why: New guess for max pages

Step 30: Allocate books: Student 1 gets 100+200=300 pages, Student 2 gets 300 pages, Student 3 gets 400+500=900 pages (exceeds 759)

Allocation not possible with max_pages=759

Why: Last student exceeds max_pages, allocation fails

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

low=760, high=759

Why: Need larger max pages to allocate

Result:

Final allocation max pages = 760
Books: [100] -> [200] -> [300] -> [400] -> [500]
Students: 3
Allocation: Student 1: 100+200+300=600, Student 2: 400, Student 3: 500
Max pages = 760

Annotated Code

DSA Python

class BookAllocator:
    def __init__(self, books, students):
        self.books = books
        self.students = students

    def can_allocate(self, max_pages):
        current_sum = 0
        required_students = 1
        for pages in self.books:
            if pages > max_pages:
                return False
            if current_sum + pages > max_pages:
                required_students += 1
                current_sum = pages
                if required_students > self.students:
                    return False
            else:
                current_sum += pages
        return True

    def find_min_max_pages(self):
        low = max(self.books)
        high = sum(self.books)
        result = high
        while low <= high:
            mid = (low + high) // 2
            if self.can_allocate(mid):
                result = mid
                high = mid - 1
            else:
                low = mid + 1
        return result


if __name__ == '__main__':
    books = [100, 200, 300, 400, 500]
    students = 3
    allocator = BookAllocator(books, students)
    min_max_pages = allocator.find_min_max_pages()
    print(min_max_pages)

if pages > max_pages: return False

Check if a single book exceeds max_pages, allocation impossible

if current_sum + pages > max_pages: required_students += 1 current_sum = pages if required_students > self.students: return False

Start new student allocation if current sum exceeds max_pages; fail if students exceed limit

while low <= high: mid = (low + high) // 2 if self.can_allocate(mid): result = mid high = mid - 1 else: low = mid + 1

Binary search on max_pages to find minimum feasible max

Output

760

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 allocation check runs 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) and very slow

Edge Cases

Only one book

Minimum max pages is pages of that single book

DSA Python

if pages > max_pages:
    return False

Number of students equals number of books

Minimum max pages is max pages of any single book

DSA Python

low = max(self.books)

Number of students is 1

Minimum max pages is sum of all books

DSA Python

high = sum(self.books)

When to Use This Pattern

When asked to split an array into subarrays minimizing the maximum sum, use binary search on the answer with a feasibility check.

Common Mistakes

Mistake: Not checking if a single book exceeds the guessed max pages, causing wrong allocation
Fix: Add a check to immediately return False if any book has pages greater than max_pages

Mistake: Updating high = mid instead of high = mid - 1 when allocation is possible, causing infinite loop
Fix: Update high = mid - 1 to shrink search space correctly

Summary

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

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

The key insight is guessing a max pages 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 when using binary search on the answer?

easy

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

B. To maximize the total pages assigned to all students

C. To find the maximum number of students that can be assigned books

D. To minimize the total number of books assigned

Solution

1. Step 1: Understand the problem goal

   The problem aims to allocate books to students such that the maximum pages assigned to any student is minimized.

2. Step 2: Clarify the binary search target

   Binary search is used on the range of possible maximum pages to find the smallest feasible maximum.

3. Final Answer:

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

4. Quick Check:

   Minimum max pages = goal [OK]

Hint: Focus on minimizing the largest pages any student gets [OK]

Common Mistakes:

• Confusing total pages with maximum pages per student
• Trying to maximize pages instead of minimizing
• Ignoring the binary search on answer approach

2. Which of the following is the correct way to initialize the binary search boundaries for the Allocate Minimum Pages problem given an array pages of book pages?

easy

A. low = sum(pages), high = max(pages)

B. low = max(pages), high = sum(pages)

C. low = 0, high = max(pages)

D. low = 0, high = sum(pages) * 2

Solution

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

   The minimum max pages is at least the largest single book (max of pages), and the maximum is the sum of all pages if one student gets all books.

2. Step 2: Set binary search boundaries accordingly

   Set low = max(pages) and high = sum(pages) to cover all feasible max page values.

3. Final Answer:

   low = max(pages), high = sum(pages) -> Option B

4. Quick Check:

   Boundaries = max and sum [OK]

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

Common Mistakes:

• Setting low to 0 which is invalid
• Swapping low and high values
• Using arbitrary high value instead of sum

3. What will be the output of the following code snippet?

def is_possible(pages, students, mid):
    count = 1
    total = 0
    for p in pages:
        if total + p > mid:
            count += 1
            total = p
            if count > students:
                return False
        else:
            total += p
    return True

pages = [10, 20, 30, 40]
students = 2
mid = 50
print(is_possible(pages, students, mid))

medium

A. True

B. None

C. SyntaxError

D. False

Solution

1. Step 1: Trace the allocation with mid = 50

   pages=[10,20,30,40], students=2: count=1, total=0 - p=10: total=10 <=50 - p=20: total=30 <=50 - p=30: 30+30=60 >50 -> count=2, total=30 - p=40: 30+40=70 >50 -> count=3 >2 -> return False

2. Step 2: Check if count exceeds students

   Count reaches 3 > 2, so return False.

3. Final Answer:

   False -> Option D

4. Quick Check:

   Allocation not possible with mid=50 = False [OK]

Hint: Check if books fit in mid pages per student [OK]

Common Mistakes:

• Miscounting students needed
• Adding pages incorrectly
• Confusing > and >= in condition

4. Identify the bug in the following code snippet for the Allocate Minimum Pages problem:

def allocate_pages(pages, students):
    low = max(pages)
    high = sum(pages)
    result = 0
    while low <= high:
        mid = (low + high) // 2
        if is_possible(pages, students, mid):
            result = mid
            low = mid + 1
        else:
            high = mid - 1
    return result

medium

A. The high pointer should move to mid - 1 when allocation is possible

B. The low pointer should move to mid + 1 when allocation is possible

C. The low pointer should move to mid when allocation is possible

D. The low pointer should move to mid - 1 when allocation is not possible

Solution

1. Step 1: Understand binary search update rules

   If allocation is possible at mid, we try to find smaller max pages by moving high to mid - 1. If not possible, we increase low to mid + 1.

2. Step 2: Identify incorrect pointer update

   The code incorrectly moves low to mid + 1 when allocation is possible instead of high to mid - 1, which searches larger values instead of smaller.

3. Final Answer:

   The high pointer should move to mid - 1 when allocation is possible -> Option A

4. Quick Check:

   Move high down when allocation succeeds [OK]

Hint: Move low up only when allocation fails, else move high down [OK]

Common Mistakes:

• Swapping low and high updates
• Not updating pointers correctly causing infinite loop
• Returning wrong result due to pointer errors

5. Given the books with pages [12, 34, 67, 90] and 3 students, what is the minimum possible maximum number of pages assigned to a student using binary search on answer?

hard

A. 67

B. 113

C. 90

D. 34

Solution

1. Step 1: Set binary search boundaries

   low = max(pages) = 90, high = sum(pages) = 203.

2. Step 2: Check feasibility at mid values

   Try mid = (90+203)//2 = 146: count=1, total=0 - p=12: total=12 <=146 - p=34: total=46 <=146 - p=67: total=113 <=146 - p=90: 113+90=203 >146 -> count=2, total=90 count=2 <=3, possible -> try smaller max Try mid = (90+145)//2 = 117: count=1, total=0 - p=12: total=12 <=117 - p=34: total=46 <=117 - p=67: total=113 <=117 - p=90: 113+90=203 >117 -> count=2, total=90 count=2 <=3, possible -> try smaller max Try mid = (90+116)//2 = 103: count=1, total=0 - p=12: total=12 <=103 - p=34: total=46 <=103 - p=67: 46+67=113 >103 -> count=2, total=67 - p=90: 67+90=157 >103 -> count=3, total=90 count=3 <=3, possible -> try smaller max Try mid = (90+102)//2 = 96: count=1, total=0 - p=12: total=12 <=96 - p=34: total=46 <=96 - p=67: 46+67=113 >96 -> count=2, total=67 - p=90: 67+90=157 >96 -> count=3, total=90 count=3 <=3, possible -> try smaller max Try mid = (90+95)//2 = 92: count=1, total=0 - p=12: total=12 <=92 - p=34: total=46 <=92 - p=67: 46+67=113 >92 -> count=2, total=67 - p=90: 67+90=157 >92 -> count=3, total=90 count=3 <=3, possible -> try smaller max Try mid = (90+91)//2 = 90: count=1, total=0 - p=12: total=12 <=90 - p=34: total=46 <=90 - p=67: 46+67=113 >90 -> count=2, total=67 - p=90: 67+90=157 >90 -> count=3, total=90 count=3 <=3, possible Try mid = (90+89)//2 = 89 (low > high, stop) Minimum max pages = 90

3. Final Answer:

   90 -> Option C

4. Quick Check:

   Minimum max pages = 90 [OK]

Hint: Binary search between max single book and total pages sum [OK]

Common Mistakes:

• Choosing max single book as answer without checking feasibility
• Not updating low and high correctly during binary search
• Misallocating books to students during checks