Allocate Minimum Pages Binary Search on Answer in DSA C - Execution Trace

Concept Flow - Allocate Minimum Pages Binary Search on Answer

Set low = max(pages array)

↓

Set high = sum(pages array)

↓

While low <= high

↓

Calculate mid = (low + high) / 2

↓

Check if allocation possible with mid

↓

Update answer = mid

↓

high = mid - 1

↓

Repeat

↓

Return answer

We use binary search on the range of possible maximum pages to find the minimum maximum pages that can be allocated to students.

Execution Sample

DSA C

int allocatePages(int pages[], int n, int m) {
  int low = max(pages, n);
  int high = sum(pages, n);
  int result = high;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (isPossible(pages, n, m, mid)) {
      result = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return result;
}

This code finds the minimum maximum pages allocated to m students by binary searching the answer.

Execution Table

Step	Operation	low	high	mid	Check Allocation Possible?	Action	Result/Answer
1	Initialize low and high	90	450	-	N/A	Set low=max pages=90, high=sum=450	-
2	Calculate mid	90	450	270	Check if allocation possible with max pages=270	Allocation possible? Yes	Update result=270, high=269
3	Calculate mid	90	269	179	Check if allocation possible with max pages=179	Allocation possible? No	Update low=180
4	Calculate mid	180	269	224	Check if allocation possible with max pages=224	Allocation possible? Yes	Update result=224, high=223
5	Calculate mid	180	223	201	Check if allocation possible with max pages=201	Allocation possible? Yes	Update result=201, high=200
6	Calculate mid	180	200	190	Check if allocation possible with max pages=190	Allocation possible? No	Update low=191
7	Calculate mid	191	200	195	Check if allocation possible with max pages=195	Allocation possible? Yes	Update result=195, high=194
8	Calculate mid	191	194	192	Check if allocation possible with max pages=192	Allocation possible? No	Update low=193
9	Calculate mid	193	194	193	Check if allocation possible with max pages=193	Allocation possible? Yes	Update result=193, high=192
10	Loop ends	193	192	-	low > high	Stop loop	Final answer=193

💡 Loop ends when low (193) > high (192), final minimum maximum pages allocated is 193

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
low	90	90	180	180	180	191	191	193	193	193
high	450	269	269	223	200	200	194	194	192	192
mid	-	270	179	224	201	190	195	192	193	-
result	450	270	270	224	201	201	195	195	193	193

Key Moments - 3 Insights

Why do we set low to the maximum pages in the array at the start?

Because no student can be allocated less than the largest single book's pages, so low starts at max pages to ensure feasibility (see Step 1 in execution_table).

Why do we update high to mid - 1 when allocation is possible?

Because if allocation is possible with mid as max pages, we try to find a smaller max by reducing high to mid - 1 (see Steps 2, 4, 5, 7, 9).

What does it mean when low becomes greater than high?

It means we have found the minimum maximum pages allocation and the search ends (see Step 10).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the value of low after this step?

A 90

B 180

C 269

D 179

💡 Hint

Check the 'low' column in execution_table row for Step 3.

At which step does the allocation become possible for the first time?

A Step 3

B Step 6

C Step 2

D Step 8

💡 Hint

Look at the 'Check Allocation Possible?' column in execution_table.

If the maximum pages in the array were increased, how would the initial low value change?

A It would increase

B It would stay the same

C It would decrease

D It would become zero

💡 Hint

Refer to variable_tracker 'low' initial value and key_moments about setting low.

Concept Snapshot

Allocate Minimum Pages using Binary Search:
- Set low = max pages in array
- Set high = sum of all pages
- While low <= high:
  - mid = (low + high) / 2
  - Check if allocation possible with mid
  - If yes, update result and high = mid - 1
  - Else, low = mid + 1
- Return result as minimum max pages

Full Transcript

This concept uses binary search on the answer range to allocate minimum maximum pages to students. We start low at the largest single book pages and high at the total pages. We check mid as a candidate max pages and verify if allocation is possible. If yes, we try smaller max by reducing high. If no, we increase low. This repeats until low exceeds high, and the last successful mid is the answer.

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