Allocate Minimum Pages Binary Search on Answer in DSA Rust

Mental Model

We want to split books into groups so that the largest group sum is as small as possible. We guess a maximum pages limit and check if we can split books within that limit.

Analogy: Imagine you have a stack of books and several friends. You want to give each friend some books so that no one carries too many pages. You guess a max pages limit and see if you can divide the books fairly under that limit.

Books: [100] -> [200] -> [300] -> [400] -> [500] -> null
Groups: |----|----|----| (3 friends)
Trying max pages limit = 500
Check if books can be split so no group has more than 500 pages.

Dry Run Walkthrough

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

Goal: Find the minimum maximum pages any friend has to read when books are divided into 3 groups

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: Calculate mid = (500 + 1500) / 2 = 1000, check if possible to split with max pages 1000

Trying max pages = 1000

Why: Check if we can split books so no group exceeds 1000 pages

Step 3: Split books: group1 = 100+200+300=600, group2 = 400, group3 = 500; all ≤ 1000, groups used = 3

Groups: [100,200,300], [400], [500]

Why: We can split into 3 groups with max pages 1000

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

low=500, high=1000

Why: Try to find smaller max pages to minimize maximum load

Step 5: Calculate mid = (500 + 1000) / 2 = 750, check if possible with max pages 750

Trying max pages = 750

Why: Check feasibility with smaller max pages

Step 6: Split books: group1 = 100+200+300=600, group2 = 400, group3 = 500; groups used = 3 and 500 ≤ 750

Groups: [100,200,300], [400], [500]

Why: Still possible with max pages 750

Step 7: Since possible, high = mid = 750

low=500, high=750

Why: Try smaller max pages again

Step 8: Calculate mid = (500 + 750) / 2 = 625, check if possible with max pages 625

Trying max pages = 625

Why: Check feasibility with even smaller max pages

Step 9: Split books: group1 = 100+200+300=600, group2 = 400, group3 = 500; groups used = 3, all ≤ 625

Groups: [100,200,300], [400], [500]

Why: Possible with max pages 625

Step 10: high = mid = 625

low=500, high=625

Why: Try smaller max pages

Step 11: Calculate mid = (500 + 625) / 2 = 562, check if possible with max pages 562

Trying max pages = 562

Why: Check feasibility with smaller max pages

Step 12: Split books: group1 = 100+200=300, group2 = 300, group3 = 400, group4 = 500; groups used = 4 > 3 friends

Groups: [100,200], [300], [400], [500]

Why: Not possible with max pages 562 because need 4 groups

Step 13: Since not possible, low = mid + 1 = 563

low=563, high=625

Why: Increase minimum max pages

Step 14: Calculate mid = (563 + 625) / 2 = 594, check if possible with max pages 594

Trying max pages = 594

Why: Check feasibility

Step 15: Split books: group1 = 100+200=300, group2 = 300, group3 = 400, group4 = 500; groups used = 4 > 3

Groups: [100,200], [300], [400], [500]

Why: Not possible with max pages 594

Step 16: low = mid + 1 = 595

low=595, high=625

Why: Increase minimum max pages

Step 17: Calculate mid = (595 + 625) / 2 = 610, check if possible with max pages 610

Trying max pages = 610

Why: Check feasibility

Step 18: Split books: group1 = 100+200+300=600, group2 = 400, group3 = 500; groups used = 3 ≤ 3

Groups: [100,200,300], [400], [500]

Why: Possible with max pages 610

Step 19: high = mid = 610

low=595, high=610

Why: Try smaller max pages

Step 20: Calculate mid = (595 + 610) / 2 = 602, check if possible with max pages 602

Trying max pages = 602

Why: Check feasibility

Step 21: Split books: group1 = 100+200+300=600, group2 = 400, group3 = 500; groups used = 3 ≤ 3

Groups: [100,200,300], [400], [500]

Why: Possible with max pages 602

Step 22: high = mid = 602

low=595, high=602

Why: Try smaller max pages

Step 23: Calculate mid = (595 + 602) / 2 = 598, check if possible with max pages 598

Trying max pages = 598

Why: Check feasibility

Step 24: Split books: group1 = 100+200=300, group2 = 300, group3 = 400, group4 = 500; groups used = 4 > 3

Groups: [100,200], [300], [400], [500]

Why: Not possible with max pages 598

Step 25: low = mid + 1 = 599

low=599, high=602

Why: Increase minimum max pages

Step 26: Calculate mid = (599 + 602) / 2 = 600, check if possible with max pages 600

Trying max pages = 600

Why: Check feasibility

Step 27: Split books: group1 = 100+200+300=600, group2 = 400, group3 = 500; groups used = 3 ≤ 3

Groups: [100,200,300], [400], [500]

Why: Possible with max pages 600

Step 28: high = mid = 600

low=599, high=600

Why: Try smaller max pages

Step 29: Calculate mid = (599 + 600) / 2 = 599, check if possible with max pages 599

Trying max pages = 599

Why: Check feasibility

Step 30: Split books: group1 = 100+200=300, group2 = 300, group3 = 400, group4 = 500; groups used = 4 > 3

Groups: [100,200], [300], [400], [500]

Why: Not possible with max pages 599

Step 31: low = mid + 1 = 600

low=600, high=600

Why: Minimum max pages found

Result:

Final minimum max pages = 600
Groups: [100,200,300], [400], [500]

Annotated Code

DSA Rust

struct Solution;

impl Solution {
    fn is_possible(books: &[i32], friends: i32, max_pages: i32) -> bool {
        let mut required_friends = 1;
        let mut current_sum = 0;
        for &pages in books {
            if pages > max_pages {
                return false; // single book exceeds max_pages
            }
            if current_sum + pages > max_pages {
                required_friends += 1; // need new friend
                current_sum = pages;
                if required_friends > friends {
                    return false; // too many friends needed
                }
            } else {
                current_sum += pages;
            }
        }
        true
    }

    pub fn allocate_minimum_pages(books: Vec<i32>, friends: i32) -> i32 {
        let mut low = *books.iter().max().unwrap_or(&0);
        let mut high: i32 = books.iter().sum();
        let mut result = high;

        while low <= high {
            let mid = low + (high - low) / 2;
            if Self::is_possible(&books, friends, mid) {
                result = mid; // possible to allocate with mid max pages
                high = mid - 1; // try smaller max pages
            } else {
                low = mid + 1; // increase max pages
            }
        }
        result
    }
}

fn main() {
    let books = vec![100, 200, 300, 400, 500];
    let friends = 3;
    let min_pages = Solution::allocate_minimum_pages(books, friends);
    println!("{}", min_pages);
}

if pages > max_pages { return false; }

Check if any single book exceeds max_pages, then allocation impossible

if current_sum + pages > max_pages { required_friends += 1; current_sum = pages; if required_friends > friends { return false; } } else { current_sum += pages; }

Start new group if adding current book exceeds max_pages; count groups needed

while low <= high { let mid = low + (high - low) / 2; if Self::is_possible(&books, friends, mid) { result = mid; high = mid - 1; } else { low = mid + 1; } }

Binary search on max_pages to find minimum feasible value

Output

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(n) for storing books array

vs Alternative: Naive approach tries all possible max pages from max book to sum, which is O(n*S) and too slow

Edge Cases

Empty books list

Returns 0 as no pages to allocate

DSA Rust

let mut low = *books.iter().max().unwrap_or(&0);

Only one friend

Returns sum of all pages as one friend reads all books

DSA Rust

let mut high: i32 = books.iter().sum();

Single book larger than any guess

is_possible returns false immediately

DSA Rust

if pages > max_pages { return false; }

When to Use This Pattern

When you need to split an array into k parts minimizing the maximum sum, use binary search on the answer to efficiently find the minimum maximum sum.

Common Mistakes

Mistake: Not checking if a single book exceeds the current max pages guess
Fix: Add a condition to return false if any single book is larger than max_pages

Mistake: Updating low and high incorrectly causing infinite loop
Fix: Use low = mid + 1 and high = mid - 1 correctly in binary search

Summary

Splits books among friends to minimize the maximum pages assigned to any friend using binary search on the answer.

Use when dividing workloads or resources into groups to balance maximum load.

The key insight is guessing a max limit and checking feasibility to narrow down the minimum possible max.

Practice

1. What is the main goal of the Allocate Minimum Pages problem 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 among students

Solution

1. Step 1: Understand the problem objective

   The problem aims to distribute book pages among students such 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 this minimum possible maximum pages value efficiently.

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: Minimize max pages per student using binary search [OK]

Common Mistakes:

• Thinking the goal is to maximize pages
• Confusing average pages with maximum pages
• Assigning pages randomly without constraints

2. Which of the following Rust function signatures correctly represents the binary search on answer approach for the Allocate Minimum Pages problem?

easy

A. fn allocate_pages(pages: &[u32], students: usize) -> u32

B. fn allocate_pages(pages: &[u32], students: u32) -> u32

C. fn allocate_pages(pages: Vec<u32>, students: u32) -> usize

D. fn allocate_pages(pages: Vec<u32>, students: usize) -> usize

Solution

1. Step 1: Analyze parameter types for pages and students

   Pages should be a slice reference &[u32] for read-only access, and students count is a u32 as a positive integer.

2. Step 2: Check return type for minimum maximum pages

   The function returns a u32 representing the minimum maximum pages allocated.

3. Final Answer:

   fn allocate_pages(pages: &[u32], students: u32) -> u32 -> Option B

4. Quick Check:

   Signature matches input slice and u32 output [OK]

Hint: Use slice &[u32] and u32 for students and return [OK]

Common Mistakes:

• Using Vec instead of slice for input when not modifying
• Mixing usize and u32 inconsistently
• Returning usize instead of u32 for pages

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

medium

A. 60

B. 50

C. 70

D. 40

Solution

1. Step 1: Calculate search range for binary search

   Minimum pages = max page = 40, maximum pages = sum = 100.

2. Step 2: Apply binary search to find minimum max pages

   Check mid = 70: possible to allocate? Yes (10+20+30=60 <=70, 40 alone). Try lower mid = 60: possible? Yes (10+20+30=60, 40 alone). Try mid = 50: possible? No (10+20=30, next 30 alone, 40 alone means 3 students needed). So minimum max pages = 60.

3. Final Answer:

   60 -> Option A

4. Quick Check:

   Minimum max pages = 60 [OK]

Hint: Check feasibility at mid, adjust search range [OK]

Common Mistakes:

• Choosing sum of all pages as answer
• Ignoring max single page as lower bound
• Miscounting number of students needed

4. Identify the bug in this Rust code snippet for checking feasibility in Allocate Minimum Pages problem:

fn is_possible(pages: &[u32], students: u32, max_pages: u32) -> bool {
    let mut count = 1;
    let mut total = 0;
    for &page in pages {
        total += page;
        if total > max_pages {
            count += 1;
            total = page;
        }
    }
    count <= students
}

medium

A. It increments count before adding page to total

B. It resets total incorrectly after exceeding max_pages

C. It does not check if a single page is greater than max_pages

D. It uses u32 instead of usize for count

Solution

1. Step 1: Understand feasibility check logic

   The function sums pages until exceeding max_pages, then assigns to next student.

2. Step 2: Identify missing check for single page size

   If any single page is larger than max_pages, allocation is impossible, but code does not check this explicitly.

3. Final Answer:

   It does not check if a single page is greater than max_pages -> Option C

4. Quick Check:

   Check single page > max_pages missing [OK]

Hint: Always check if any single page exceeds max_pages [OK]

Common Mistakes:

• Ignoring single page size check
• Resetting total before incrementing count
• Using wrong variable types causing overflow

5. You have pages array [12, 34, 67, 90] and 2 students. Using binary search on answer, what is the minimum maximum pages allocation? Also, explain why the naive approach of assigning equal pages to each student might fail.

hard

A. 67; Naive approach fails due to uneven page sizes

B. 124; Naive approach always works for equal distribution

C. 90; Naive approach is optimal for sorted pages

D. 113; Naive approach ignores page order and max page size

Solution

1. Step 1: Calculate binary search range and feasibility

   Max single page = 90, sum = 203. Check mid = 113: allocate (12+34+67=113) to first student, 90 to second student. Possible. Try lower mid = 101: (12+34=46, next 67 alone, 90 alone) needs 3 students, not possible. So minimum max pages = 113.

2. Step 2: Explain naive approach failure

   Naive approach divides total pages (203) by students (2) = 101.5, but cannot split pages arbitrarily or ignore max single page size, so it fails to find feasible allocation.

3. Final Answer:

   113; Naive approach ignores page order and max page size -> Option D

4. Quick Check:

   Minimum max pages = 113; naive fails due to constraints [OK]

Hint: Check max single page and feasibility, naive ignores constraints [OK]

Common Mistakes:

• Assuming equal division always works
• Ignoring max single page size
• Not testing feasibility with actual page grouping