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

↓

high = mid-1

↓

Repeat loop

↓

Return low as minimum pages

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

Execution Sample

DSA C++

int allocatePages(int pages[], int n, int students) {
  int low = *max_element(pages, pages + n), high = 0;
  for (int i = 0; i < n; i++) high += pages[i];
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (canAllocate(pages, n, students, mid)) high = mid - 1;
    else low = mid + 1;
  }
  return low;
}

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

Execution Table

Step	Operation	mid (max pages)	Allocation Possible?	low	high	Visual State
1	Initialize low and high	N/A	N/A	max pages = 90	sum pages = 250	[90, 40, 30, 50, 40]
2	Calculate mid	170	Check allocation with max 170 pages	90	250	[90, 40, 30, 50, 40]
3	Allocation check	170	Yes	90	250	Allocate: Student1:90+40+30=160, Student2:50+40=90
4	Update high	170	N/A	90	169	[90, 40, 30, 50, 40]
5	Calculate mid	129	Check allocation with max 129 pages	90	169	[90, 40, 30, 50, 40]
6	Allocation check	129	Yes	90	169	Allocate: Student1:90, Student2:40+30+50=120, Student3:40
7	Update high	129	N/A	90	128	[90, 40, 30, 50, 40]
8	Calculate mid	109	Check allocation with max 109 pages	90	128	[90, 40, 30, 50, 40]
9	Allocation check	109	No	90	128	Allocate: Student1:90, Student2:40+30=70, Student3:50+40=90 (3 students needed, but only 2 available)
10	Update low	109	N/A	110	128	[90, 40, 30, 50, 40]
11	Calculate mid	119	Check allocation with max 119 pages	110	128	[90, 40, 30, 50, 40]
12	Allocation check	119	Yes	110	128	Allocate: Student1:90, Student2:40+30=70, Student3:50+40=90
13	Update high	119	N/A	110	118	[90, 40, 30, 50, 40]
14	Calculate mid	114	Check allocation with max 114 pages	110	118	[90, 40, 30, 50, 40]
15	Allocation check	114	No	110	118	Allocate: Student1:90, Student2:40+30=70, Student3:50+40=90 (3 students needed, only 2 available)
16	Update low	114	N/A	115	118	[90, 40, 30, 50, 40]
17	Calculate mid	116	Check allocation with max 116 pages	115	118	[90, 40, 30, 50, 40]
18	Allocation check	116	Yes	115	118	Allocate: Student1:90, Student2:40+30=70, Student3:50+40=90
19	Update high	116	N/A	115	115	[90, 40, 30, 50, 40]
20	Calculate mid	115	Check allocation with max 115 pages	115	115	[90, 40, 30, 50, 40]
21	Allocation check	115	No	115	115	Allocate: Student1:90, Student2:40+30=70, Student3:50+40=90 (3 students needed, only 2 available)
22	Update low	115	N/A	116	115	[90, 40, 30, 50, 40]
23	Exit loop	N/A	low > high	116	115	[90, 40, 30, 50, 40]

💡 Loop ends when low (116) > high (115), minimum max pages is 116

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 10	After Step 11	After Step 14	After Step 16	After Step 19	After Step 22	Final
low	90	90	90	90	110	110	110	115	115	116	116
high	250	250	169	128	128	128	118	118	115	115	115
mid	N/A	170	129	109	109	119	114	116	116	115	N/A

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 lower than that is impossible. See Step 1 in execution_table.

Why does the allocation check sometimes require more students than available?

If mid is too small, books can't be grouped within that max pages limit, so more students are needed. This is shown in Steps 9 and 15 where allocation fails.

Why do we update low to mid + 1 when allocation is not possible?

Because mid is too small to allocate all books, we must try a larger max pages value. See Steps 10 and 16 for this update.

Visual Quiz - 3 Questions

Look at the execution_table at Step 6, is allocation possible with mid = 129?

A Yes, allocation is possible with 3 students

B No, allocation is not possible

C Yes, allocation is possible with 2 students

D No, allocation requires more than 3 students

💡 Hint

Check the 'Allocation Possible?' column at Step 6 in execution_table

At which step does the condition low <= high become false, ending the loop?

A Step 22

B Step 23

C Step 21

D Step 20

💡 Hint

Look at the exit_note and Step 23 in execution_table

If the largest book had 100 pages instead of 90, what would be the new initial low value?

A 90

B 250

C 100

D 170

💡 Hint

Initial low is max pages of a single book, see Step 1 in execution_table

Concept Snapshot

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

Full Transcript

This concept uses binary search on the answer space to find the minimum maximum pages that can be allocated to students. We start with low as the largest single book pages and high as the total pages. We repeatedly check if allocation is possible with mid as max pages. If yes, we try smaller max by moving high down. If no, we increase low. The process continues until low exceeds high, and low is the answer.