Allocate Minimum Pages Binary Search on Answer in DSA C

Mental Model

We want to split books among students so that the largest number of pages any student gets 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 group of friends. You want to give books to each friend so no one gets too many pages. You try a guess for the max pages per friend and see if it works. If it does, you try smaller max pages; if not, you try bigger max pages.

Books: [100] -> [200] -> [300] -> [400] -> null
Students: 3
Trying max pages = 500
Allocation:
Student1: 100 -> 200 (sum=300 ≤ 500)
Student2: 300 (sum=300 ≤ 500)
Student3: 400 (sum=400 ≤ 500)

Dry Run Walkthrough

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

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

Step 1: Set low to max book pages (400), high to sum of all pages (1000), mid = (400+1000)/2 = 700

low=400, high=1000, mid=700

Why: We start binary search between max single book and total pages

Step 2: Check if allocation possible with max pages = 700

Student1: 100+200+300=600 ≤ 700
Student2: 400 ≤ 700
Students used: 2 ≤ 3

Why: Allocation fits in 2 students, so 700 is a valid max pages

Step 3: Since 700 works, try smaller max pages: high = mid - 1 = 699

low=400, high=699

Why: Try to find smaller max pages to minimize maximum

Step 4: Calculate new mid = (400+699)/2 = 549, check allocation with max pages = 549

Student1: 100+200=300 ≤ 549
Student2: 300 ≤ 549
Student3: 400 ≤ 549
Students used: 3 ≤ 3

Why: Allocation fits exactly in 3 students, so 549 is valid

Step 5: Try smaller max pages: high = 548

low=400, high=548

Why: Try to reduce max pages further

Step 6: Calculate mid = (400+548)/2 = 474, check allocation with max pages = 474

Student1: 100+200=300 ≤ 474
Student2: 300 ≤ 474
Student3: 400 ≤ 474
Students used: 3 ≤ 3

Why: Allocation fits in 3 students, 474 is valid

Step 7: Try smaller max pages: high = 473

low=400, high=473

Why: Try to reduce max pages further

Step 8: Calculate mid = (400+473)/2 = 436, check allocation with max pages = 436

Student1: 100+200=300 ≤ 436
Student2: 300 ≤ 436
Student3: 400 ≤ 436
Students used: 3 ≤ 3

Why: Allocation fits in 3 students, 436 is valid

Step 9: Try smaller max pages: high = 435

low=400, high=435

Why: Try to reduce max pages further

Step 10: Calculate mid = (400+435)/2 = 417, check allocation with max pages = 417

Student1: 100+200=300 ≤ 417
Student2: 300 ≤ 417
Student3: 400 ≤ 417
Students used: 3 ≤ 3

Why: Allocation fits in 3 students, 417 is valid

Step 11: Try smaller max pages: high = 416

low=400, high=416

Why: Try to reduce max pages further

Step 12: Calculate mid = (400+416)/2 = 408, check allocation with max pages = 408

Student1: 100+200=300 ≤ 408
Student2: 300 ≤ 408
Student3: 400 ≤ 408
Students used: 3 ≤ 3

Why: Allocation fits in 3 students, 408 is valid

Step 13: Try smaller max pages: high = 407

low=400, high=407

Why: Try to reduce max pages further

Step 14: Calculate mid = (400+407)/2 = 403, check allocation with max pages = 403

Student1: 100+200=300 ≤ 403
Student2: 300 ≤ 403
Student3: 400 ≤ 403
Students used: 3 ≤ 3

Why: Allocation fits in 3 students, 403 is valid

Step 15: Try smaller max pages: high = 402

low=400, high=402

Why: Try to reduce max pages further

Step 16: Calculate mid = (400+402)/2 = 401, check allocation with max pages = 401

Student1: 100+200=300 ≤ 401
Student2: 300 ≤ 401
Student3: 400 ≤ 401
Students used: 3 ≤ 3

Why: Allocation fits in 3 students, 401 is valid

Step 17: Try smaller max pages: high = 400

low=400, high=400

Why: Try to reduce max pages further

Step 18: Calculate mid = (400+400)/2 = 400, check allocation with max pages = 400

Student1: 100+200=300 ≤ 400
Student2: 300 ≤ 400
Student3: 400 ≤ 400
Students used: 3 ≤ 3

Why: Allocation fits in 3 students, 400 is valid

Step 19: Try smaller max pages: high = 399

low=400, high=399

Why: Now high < low, stop search

Result:

Final minimum max pages = 400
Allocation:
Student1: 100 + 200 = 300
Student2: 300
Student3: 400

Annotated Code

DSA C

#include <stdio.h>

int canAllocate(int books[], int n, int students, int maxPages) {
    int requiredStudents = 1;
    int currentSum = 0;
    for (int i = 0; i < n; i++) {
        if (books[i] > maxPages) {
            return 0; // single book exceeds maxPages, not possible
        }
        if (currentSum + books[i] > maxPages) {
            requiredStudents++;
            currentSum = books[i];
            if (requiredStudents > students) {
                return 0; // need more students than available
            }
        } else {
            currentSum += books[i];
        }
    }
    return 1;
}

int allocateMinimumPages(int books[], int n, int students) {
    int low = 0, high = 0;
    for (int i = 0; i < n; i++) {
        if (books[i] > low) {
            low = books[i];
        }
        high += books[i];
    }
    int result = high;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canAllocate(books, n, students, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    int books[] = {100, 200, 300, 400};
    int students = 3;
    int n = sizeof(books) / sizeof(books[0]);
    int minPages = allocateMinimumPages(books, n, students);
    printf("%d\n", minPages);
    return 0;
}

if (books[i] > maxPages) { return 0; }

Check if a single book exceeds maxPages, allocation impossible

if (currentSum + books[i] > maxPages) { requiredStudents++; currentSum = books[i]; if (requiredStudents > students) return 0; } else { currentSum += books[i]; }

Allocate books to current student until sum exceeds maxPages, then move to next student

for (int i = 0; i < n; i++) { if (books[i] > low) low = books[i]; high += books[i]; }

Initialize low as max single book pages, high as sum of all pages

while (low <= high) { int mid = low + (high - low) / 2; if (canAllocate(...)) { result = mid; high = mid - 1; } else { low = mid + 1; } }

Binary search to find minimum max pages that allows allocation

Output

400

Complexity Analysis

Time: O(n log S) because we do binary search on the range of sum of pages S, and each check takes O(n) to verify allocation

Space: O(1) because we use only a few variables, no extra data structures proportional to input size

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

Number of students is 1

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

DSA C

int result = high;

Number of students equals number of books

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

DSA C

if (books[i] > low) low = books[i];

A book has more pages than any guessed maxPages

Allocation fails immediately, function returns 0

DSA C

if (books[i] > maxPages) { return 0; }

When to Use This Pattern

When you need to split a list into parts minimizing the maximum sum per part, use binary search on the answer to efficiently find the optimal maximum sum.

Common Mistakes

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

Mistake: Not checking if a single book exceeds the current maxPages guess in canAllocate
Fix: Add a check to return false if any book is larger than maxPages

Mistake: Allocating books out of order or skipping books
Fix: Always allocate books in given order without skipping to maintain problem constraints

Summary

It finds the smallest maximum number of pages assigned to any student when books are allocated in order.

Use it when you want to divide a sequence into parts minimizing the largest sum among parts.

The key insight is to guess the answer and check feasibility using binary search on the answer space.

Practice

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

easy

A. To maximize the total number of pages assigned

B. To find the average number of pages per student

C. To minimize the maximum number of pages assigned to any student

D. To assign pages randomly to students

Solution

1. Step 1: Understand the problem goal

   The problem wants to divide 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 any student -> Option C

4. Quick Check:

   Goal = minimize max pages per student [OK]

Hint: Focus on minimizing the max pages per student, not total pages [OK]

Common Mistakes:

• Confusing total pages with maximum pages per student
• Thinking binary search finds average pages
• Assuming random assignment solves the problem

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

easy

A. int low = max_page_count, high = sum_of_all_pages;

B. int low = 0, high = sum_of_all_pages;

C. int low = 0, high = max_page_count;

D. int low = sum_of_all_pages, high = max_page_count;

Solution

1. Step 1: Determine the search boundaries

   The minimum possible max pages is at least the largest single book (max_page_count), and the maximum possible is the sum of all pages.

2. Step 2: Set binary search range accordingly

   So, low = max_page_count and high = sum_of_all_pages is correct initialization.

3. Final Answer:

   int low = max_page_count, high = sum_of_all_pages; -> Option A

4. Quick Check:

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

Hint: Start low at max single book pages, high at total pages sum [OK]

Common Mistakes:

• Starting low at 0 instead of max book pages
• Swapping low and high values
• Using arbitrary values outside page counts

3. Given the array of pages [10, 20, 30, 40] and 2 students, what is the minimum maximum pages assigned to a student?

medium

A. 30

B. 50

C. 40

D. 60

Solution

1. Step 1: Check possible max pages assignments

   Try to split books into 2 parts so max pages per student is minimized. Possible splits: [10,20,30] and [40] max 60; [10,20] and [30,40] max 70; [10,20,30,40] all to one student max 100.

2. Step 2: Use binary search or reasoning

   Splitting as [10,20] and [30,40] gives max 70, but [10,20,30] and [40] gives max 60. Check if 50 is possible: [10,20] and [30,40] max 70 too high, but [10,20,30] is 60. So 50 is not possible because 40 > 50. So minimum max pages is 60.

3. Final Answer:

   60 -> Option D

4. Quick Check:

   Minimum max pages = 60 [OK]

Hint: Try splitting books to minimize max pages per student [OK]

Common Mistakes:

• Choosing max single book as answer without checking splits
• Assuming equal split always works
• Ignoring that a student must get continuous books

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

int isPossible(int arr[], int n, int m, int mid) {
    int studentCount = 1, pageSum = 0;
    for (int i = 0; i < n; i++) {
        if (pageSum + arr[i] <= mid) {
            pageSum += arr[i];
        } else {
            studentCount++;
            pageSum = arr[i];
        }
    }
    return studentCount <= m;
}

medium

A. It does not check if a single book has more pages than mid

B. It increments studentCount incorrectly

C. It should return studentCount >= m instead

D. It does not initialize pageSum to arr[0]

Solution

1. Step 1: Analyze feasibility check logic

   The function tries to assign books to students without exceeding mid pages per student.

2. Step 2: Identify missing check

   If a single book has pages more than mid, the function still tries to assign it, which is invalid. This case is not handled.

3. Final Answer:

   It does not check if a single book has more pages than mid -> Option A

4. Quick Check:

   Check single book pages <= mid [OK]

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

Common Mistakes:

• Ignoring single book size check
• Returning wrong comparison for studentCount
• Incorrect initialization of pageSum

5. You have books with pages [12, 34, 67, 90] and 2 students. Using binary search on answer, what is the minimum maximum pages a student can get? Explain the steps.

hard

A. 101

B. 113

C. 90

D. 67

Solution

1. Step 1: Set binary search range

   Minimum max pages = max single book = 90, maximum = sum = 12+34+67+90=203.

2. Step 2: Apply binary search and feasibility check

   Mid = (90+203)/2=146. Check if possible with max 146 pages: assign [12,34,67] sum=113 to student1, [90] to student2. Possible. Try lower mid.

3. Step 3: Narrow down mid

   Mid = (90+146)/2=118. Check with 118: assign [12,34,67] sum=113 student1, [90] student2. Possible. Try lower mid.

4. Step 4: Check mid=104

   Assign [12,34] sum=46 student1, [67,90] sum=157 student2 exceeds 104. Not possible.

5. Step 5: Check mid=111

   Assign [12,34,67] sum=113 >111 no. Assign [12,34] sum=46 student1, [67,90] sum=157 no. Not possible.

6. Step 6: Check mid=113

   Assign [12,34,67] sum=113 student1, [90] student2. Possible.

7. Step 7: Final minimum max pages

   Minimum max pages = 113.

8. Final Answer:

   113 -> Option B

9. Quick Check:

   Minimum max pages = 113 [OK]

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

Common Mistakes:

• Choosing max single book as answer without checking splits
• Not testing feasibility properly
• Confusing sum and max in binary search range