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

Concept Flow - Allocate Minimum Pages Binary Search on Answer

Set low = max(pages array)

↓

Set high = sum(pages array)

↓

While low <= high

↓

mid = (low+high)/2

↓

Check if allocation possible with mid

↓

If possible

Yes→Update answer = mid

↓

high = mid - 1

↓

low = mid + 1

↓

Return answer

We use binary search on the range of possible maximum pages to allocate, checking feasibility each time, narrowing down to the minimum maximum pages.

Execution Sample

DSA Java

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

This code finds the minimum maximum pages per student by binary searching between max single book pages and total pages.

Execution Table

Step	Operation	low	high	mid	Can Allocate?	Action	Result (answer)
1	Initialize low and high	50	250	-	-	Set low=50, high=250	-
2	Calculate mid	50	250	150	-	mid = (50+250)/2 = 150	-
3	Check allocation with mid=150	50	250	150	Yes	Allocation possible, update answer=150	150
4	Update high	50	149	150	Yes	high = mid - 1 = 149	150
5	Calculate mid	50	149	99	-	mid = (50+149)/2 = 99	150
6	Check allocation with mid=99	50	149	99	No	Allocation not possible, update low=mid+1=100	150
7	Calculate mid	100	149	124	-	mid = (100+149)/2 = 124	150
8	Check allocation with mid=124	100	149	124	Yes	Allocation possible, update answer=124	124
9	Update high	100	123	124	Yes	high = mid - 1 = 123	124
10	Calculate mid	100	123	111	-	mid = (100+123)/2 = 111	124
11	Check allocation with mid=111	100	123	111	Yes	Allocation possible, update answer=111	111
12	Update high	100	110	111	Yes	high = mid - 1 = 110	111
13	Calculate mid	100	110	105	-	mid = (100+110)/2 = 105	111
14	Check allocation with mid=105	100	110	105	No	Allocation not possible, update low=mid+1=106	111
15	Calculate mid	106	110	108	-	mid = (106+110)/2 = 108	111
16	Check allocation with mid=108	106	110	108	Yes	Allocation possible, update answer=108	108
17	Update high	106	107	108	Yes	high = mid - 1 = 107	108
18	Calculate mid	106	107	106	-	mid = (106+107)/2 = 106	108
19	Check allocation with mid=106	106	107	106	No	Allocation not possible, update low=mid+1=107	108
20	Calculate mid	107	107	107	-	mid = (107+107)/2 = 107	108
21	Check allocation with mid=107	107	107	107	Yes	Allocation possible, update answer=107	107
22	Update high	107	106	107	Yes	high = mid - 1 = 106	107
23	Exit loop	107	106	-	-	low > high, stop	107

💡 Loop ends when low (107) > high (106), final answer is 107

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	After Step 10	After Step 13	After Step 15	After Step 18	After Step 20	Final
low	50	50	50	100	100	100	106	106	107	107
high	250	250	149	149	123	110	110	107	107	106
mid	-	150	99	124	111	105	108	106	107	-
answer	250	250	150	150	124	111	111	108	108	107

Key Moments - 3 Insights

Why do we start low with the maximum single book pages?

Because no student can be assigned less than the largest book's pages, starting low below that would be impossible. See execution_table step 1 where low is set to 50, the max pages.

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

Because we try to find a smaller maximum pages allocation, so we reduce the upper bound. This is shown in execution_table steps 4, 9, 12, 17, and 22.

What does 'Can Allocate?' mean in the table?

'Can Allocate?' means checking if we can assign books to students so that no student gets more than mid pages. If yes, we try smaller mid; if no, we increase mid. See steps 3, 6, 8, 11, 14, 16, 19, 21.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of 'low' after this step?

A 50

B 99

C 100

D 150

💡 Hint

Check the 'Action' column at step 6 where low is updated to mid + 1 = 100.

At which step does the 'answer' variable first update to 111?

A Step 10

B Step 11

C Step 14

D Step 9

💡 Hint

Look at the 'Result (answer)' column and find when it changes to 111.

If the initial 'low' was set to 40 instead of 50, what would happen in the execution_table?

A The algorithm would fail because low is less than max pages.

B The algorithm would still work but take more iterations.

C The algorithm would immediately return 40.

D The algorithm would skip the binary search loop.

💡 Hint

Refer to key_moments about why low starts at max pages (step 1).

Concept Snapshot

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

Full Transcript

This concept uses binary search to find the minimum maximum number of pages that can be allocated to students. We start with low as the maximum pages in a single book and high as the sum of all pages. We repeatedly check the middle value mid to see if allocation is possible without exceeding mid pages per student. If possible, we try to find a smaller maximum by moving high down. If not, we increase low. This continues 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 using binary search on 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 asks to allocate books to students so 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 the minimum possible maximum pages that can be assigned to a 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 assigned [OK]

Common Mistakes:

• Thinking the goal is to maximize pages
• Confusing average pages with maximum pages
• Assuming random allocation is acceptable

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

easy

A. int low = 0; int high = max pages in a single book;

B. int low = 0; int high = sum of all pages;

C. int low = max pages in a single book; int high = sum of all pages;

D. int low = sum of all pages; int high = max pages in a single book;

Solution

1. Step 1: Determine the minimum possible max pages

   The minimum max pages must be at least the largest single book's pages, because no book can be split.

2. Step 2: Determine the maximum possible max pages

   The maximum max pages is the sum of all pages if one student gets all books.

3. Final Answer:

   int low = max pages in a single book; int high = sum of all pages; -> Option C

4. Quick Check:

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

Hint: Low = max single book, High = sum all pages [OK]

Common Mistakes:

• Setting low to 0 which is invalid
• Swapping low and high values
• Using average pages as boundaries

3. Consider the books with pages [10, 20, 30, 40] and 2 students. What is the minimum maximum pages allocated to a student?

medium

A. 40

B. 70

C. 50

D. 60

Solution

1. Step 1: Check possible max pages allocations

   Try to split books so that max pages per student is minimized. Possible splits: [10,20,30] and [40] max=60; or [10,20] and [30,40] max=70.

2. Step 2: Choose minimum max pages

   Between 60 and 70, 60 is smaller and valid allocation.

3. Final Answer:

   60 -> Option D

4. Quick Check:

   Minimum max pages = 60 [OK]

Hint: Try splits and pick smallest max sum [OK]

Common Mistakes:

• Choosing sum of all pages as answer
• Ignoring largest single book pages
• Incorrectly splitting books

4. Given the following code snippet for checking feasibility in the Allocate Minimum Pages problem, what is the bug?

boolean isPossible(int[] pages, int students, int mid) {
    int count = 1, sum = 0;
    for (int page : pages) {
        sum += page;
        if (sum > mid) {
            count++;
            sum = 0;
        }
    }
    return count <= students;
}

medium

A. sum should be reset to current page, not zero, after count increment

B. count should be reset to zero inside the loop

C. The loop should start from index 1, not zero

D. The function should return count >= students

Solution

1. Step 1: Analyze sum reset logic

   When sum exceeds mid, count increments but sum resets to zero, losing the current page's value.

2. Step 2: Correct sum reset to current page

   Sum should reset to current page's value to include it in the new student's allocation.

3. Final Answer:

   sum should be reset to current page, not zero, after count increment -> Option A

4. Quick Check:

   Reset sum = current page [OK]

Hint: Reset sum to current page, not zero [OK]

Common Mistakes:

• Resetting sum to zero loses current page
• Returning wrong comparison for count and students
• Incorrect loop indexing

5. You have books with pages [12, 34, 67, 90] and 2 students. Using binary search on answer, what is the minimum maximum pages that can be allocated to a student? Show the reasoning.

hard

A. 90

B. 113

C. 101

D. 67

Solution

1. Step 1: Set binary search boundaries

   Low = max single book pages = 90, High = sum = 12+34+67+90=203.

2. Step 2: Check mid and feasibility

   Mid = (90+203)/2=146. Check if allocation possible with max 146 pages per student: [12,34,67] sum=113 <=146, next student gets [90]. Possible with 2 students.

3. Step 3: Narrow search

   Try lower mid: (90+146)/2=118. Check allocation: [12,34,67] sum=113 <=118, next student [90]. Possible.

4. Step 4: Try even lower mid

   Mid = (90+118)/2=104. Allocation: [12,34,67] sum=113 >104, so split: [12,34] sum=46 <=104, next student [67,90] sum=157 >104 not possible.

5. Step 5: Increase low to 105 and continue

   Mid = (105+118)/2=111. Allocation: [12,34,67] sum=113 >111 no, split: [12,34] sum=46 <=111, next student [67,90] sum=157 >111 no.

6. Step 6: Mid = (112+118)/2=115

   Allocation: [12,34,67] sum=113 <=115 yes, next student [90]. Possible.

7. Step 7: Narrow down to minimum feasible

   Try mid= (112+114)/2=113 allocation possible, mid=112 allocation not possible.

8. Final Answer:

   113 -> Option B

9. Quick Check:

   Minimum max pages = 113 [OK]

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

Common Mistakes:

• Choosing max single book pages as answer
• Not checking feasibility correctly
• Stopping binary search too early