Allocate Minimum Pages Binary Search on Answer in DSA Go

Mental Model

We want to split books among students so that the largest pages assigned to any student is as small as possible. We guess a maximum pages limit and check if we can allocate books within that limit.

Analogy: Imagine dividing a pile of books among friends so that no one carries too many pages. You try a weight limit and see if everyone can carry their share without exceeding it.

Books: [100] -> [200] -> [300] -> [400] -> null
Students: 2
Trying max pages limit: 500
Allocation example:
Student 1: 100 -> 200 -> 300 (total 600 > 500 not allowed)
Student 2: 400
So 500 is too small, try bigger limit.

Dry Run Walkthrough

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

Goal: Find the minimum maximum pages any student has to read when books are divided among 2 students

Step 1: Set low to max book pages (400), high to sum of all pages (1000), start binary search

low=400, high=1000

Why: Minimum max pages can't be less than largest book, max can't be more than total pages

Step 2: Check mid = (400+1000)/2 = 700, try to allocate books with max pages 700

Try allocation with max_pages=700

Why: Test if 700 is a valid max pages limit

Step 3: Allocate books: Student 1 gets 100+200+300=600 (<=700), Student 2 gets 400 (<=700)

Allocation possible with max_pages=700

Why: 700 works, try smaller max to minimize

Step 4: Set high = mid - 1 = 699, binary search continues

low=400, high=699

Why: Try smaller max pages to find minimum

Step 5: Check mid = (400+699)/2 = 549, try allocation with max pages 549

Try allocation with max_pages=549

Why: Test if 549 is valid max pages limit

Step 6: Allocate books: Student 1 gets 100+200=300 (<=549), next book 300 would exceed 549, so Student 2 gets 300+400=700 (>549) not allowed

Allocation not possible with max_pages=549

Why: 549 too small, need bigger max pages

Step 7: Set low = mid + 1 = 550, binary search continues

low=550, high=699

Why: Increase max pages to allow allocation

Step 8: Check mid = (550+699)/2 = 624, try allocation with max pages 624

Try allocation with max_pages=624

Why: Test if 624 is valid max pages limit

Step 9: Allocate books: Student 1 gets 100+200+300=600 (<=624), Student 2 gets 400 (<=624)

Allocation possible with max_pages=624

Why: 624 works, try smaller max

Step 10: Set high = mid - 1 = 623, binary search continues

low=550, high=623

Why: Try smaller max pages

Step 11: Check mid = (550+623)/2 = 586, try allocation with max pages 586

Try allocation with max_pages=586

Why: Test if 586 is valid max pages limit

Step 12: Allocate books: Student 1 gets 100+200=300 (<=586), next book 300 would exceed 586, Student 2 gets 300+400=700 (>586) not allowed

Allocation not possible with max_pages=586

Why: 586 too small

Step 13: Set low = mid + 1 = 587, binary search continues

low=587, high=623

Why: Increase max pages

Step 14: Check mid = (587+623)/2 = 605, try allocation with max pages 605

Try allocation with max_pages=605

Why: Test if 605 is valid max pages limit

Step 15: Allocate books: Student 1 gets 100+200+300=600 (<=605), Student 2 gets 400 (<=605)

Allocation possible with max_pages=605

Why: 605 works, try smaller max

Step 16: Set high = mid - 1 = 604, binary search continues

low=587, high=604

Why: Try smaller max pages

Step 17: Check mid = (587+604)/2 = 595, try allocation with max pages 595

Try allocation with max_pages=595

Why: Test if 595 is valid max pages limit

Step 18: Allocate books: Student 1 gets 100+200=300 (<=595), next book 300 would exceed 595, Student 2 gets 300+400=700 (>595) not allowed

Allocation not possible with max_pages=595

Why: 595 too small

Step 19: Set low = mid + 1 = 596, binary search continues

low=596, high=604

Why: Increase max pages

Step 20: Check mid = (596+604)/2 = 600, try allocation with max pages 600

Try allocation with max_pages=600

Why: Test if 600 is valid max pages limit

Step 21: Allocate books: Student 1 gets 100+200+300=600 (<=600), Student 2 gets 400 (<=600)

Allocation possible with max_pages=600

Why: 600 works, try smaller max

Step 22: Set high = mid - 1 = 599, binary search continues

low=596, high=599

Why: Try smaller max pages

Step 23: Check mid = (596+599)/2 = 597, try allocation with max pages 597

Try allocation with max_pages=597

Why: Test if 597 is valid max pages limit

Step 24: Allocate books: Student 1 gets 100+200=300 (<=597), next book 300 would exceed 597, Student 2 gets 300+400=700 (>597) not allowed

Allocation not possible with max_pages=597

Why: 597 too small

Step 25: Set low = mid + 1 = 598, binary search continues

low=598, high=599

Why: Increase max pages

Step 26: Check mid = (598+599)/2 = 598, try allocation with max pages 598

Try allocation with max_pages=598

Why: Test if 598 is valid max pages limit

Step 27: Allocate books: Student 1 gets 100+200=300 (<=598), next book 300 would exceed 598, Student 2 gets 300+400=700 (>598) not allowed

Allocation not possible with max_pages=598

Why: 598 too small

Step 28: Set low = mid + 1 = 599, binary search continues

low=599, high=599

Why: Increase max pages

Step 29: Check mid = (599+599)/2 = 599, try allocation with max pages 599

Try allocation with max_pages=599

Why: Test if 599 is valid max pages limit

Step 30: Allocate books: Student 1 gets 100+200=300 (<=599), next book 300 would exceed 599, Student 2 gets 300+400=700 (>599) not allowed

Allocation not possible with max_pages=599

Why: 599 too small

Step 31: Set low = mid + 1 = 600, now low > high, binary search ends

low=600, high=599

Why: Search space exhausted, minimum max pages found

Result:

Final allocation max pages = 600
Books allocation:
Student 1: 100 -> 200 -> 300 -> null
Student 2: 400 -> null

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type Books []int

func canAllocate(books Books, students int, maxPages int) bool {
	count := 1
	currentSum := 0
	for _, pages := range books {
		if pages > maxPages {
			return false // single book exceeds maxPages
		}
		if currentSum+pages > maxPages {
			count++ // allocate to next student
			currentSum = pages
			if count > students {
				return false // need more students than available
			}
		} else {
			currentSum += pages
		}
	}
	return true
}

func allocateMinimumPages(books Books, students int) int {
	low := 0
	high := 0
	for _, pages := range books {
		if pages > low {
			low = pages // max single book pages
		}
		high += pages // sum of all pages
	}
	result := high
	for low <= high {
		mid := (low + high) / 2
		if canAllocate(books, students, mid) {
			result = mid
			high = mid - 1 // try smaller max pages
		} else {
			low = mid + 1 // increase max pages
		}
	}
	return result
}

func main() {
	books := Books{100, 200, 300, 400}
	students := 2
	minPages := allocateMinimumPages(books, students)
	fmt.Printf("Minimum maximum pages allocated: %d\n", minPages)
}

if pages > maxPages { return false }

Check if a single book exceeds current max pages limit

if currentSum+pages > maxPages { count++; currentSum = pages; if count > students { return false } } else { currentSum += pages }

Allocate books to students without exceeding max pages; move to next student if needed

for _, pages := range books { if pages > low { low = pages }; high += pages }

Initialize binary search bounds: low=max single book, high=sum all pages

mid := (low + high) / 2

Calculate mid as candidate max pages

if canAllocate(books, students, mid) { result = mid; high = mid - 1 } else { low = mid + 1 }

Adjust binary search bounds based on feasibility

Output

Minimum maximum pages allocated: 600

Complexity Analysis

Time: O(n log m) where n is number of books and m is sum of pages; binary search runs log m times and allocation check runs 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*m) and inefficient

Edge Cases

Only one student

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

DSA Go

if count > students { return false }

Number of students equals number of books

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

DSA Go

if pages > maxPages { return false }

A book has more pages than any guessed max pages

Allocation fails immediately because no student can read that book within max pages

DSA Go

if pages > maxPages { return false }

When to Use This Pattern

When asked to split an array into subarrays minimizing the maximum sum, use binary search on the answer space combined with a feasibility check.

Common Mistakes

Mistake: Setting low to 0 instead of max book pages, causing invalid guesses
Fix: Initialize low to max pages of a single book to ensure valid search space

Mistake: Not checking if a single book exceeds max pages in feasibility function
Fix: Add check to return false if any book pages > maxPages

Mistake: Incrementing student count incorrectly or forgetting to reset current sum
Fix: Increment student count only when current sum + pages exceeds maxPages and reset current sum to current book pages

Summary

It finds the smallest maximum pages assigned to any student when dividing books.

Use it when you must split an array into parts minimizing the largest sum part.

The key insight is guessing a max pages limit and checking if allocation is possible, then narrowing guesses with binary search.

Practice

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

easy

A. To maximize the total number of pages assigned

B. To minimize the maximum number of pages assigned to a student

C. To find the student with the least pages

D. To count the total number of pages in all books

Solution

1. Step 1: Understand the problem objective

   The problem asks to allocate books to students such that the maximum pages assigned to any student is minimized.

2. Step 2: Identify the binary search approach

   We use binary search on the range of possible maximum pages to find the minimum feasible maximum.

3. Final Answer:

   To minimize the maximum number of pages assigned to a student -> Option B

4. Quick Check:

   Goal = minimize max pages [OK]

Hint: Minimize max pages per student using binary search [OK]

Common Mistakes:

• Confusing minimizing max pages with maximizing total pages
• Thinking the problem counts students instead of pages
• Ignoring the binary search on answer approach

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

easy

A. low := 0; high := sum of all pages

B. low := 0; high := max pages in a single book

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

D. low := number of students; high := number of books

Solution

1. Step 1: Determine minimum and maximum boundaries

   The minimum possible max pages is the largest single book pages, because no book can be split.

2. Step 2: Set high boundary as total pages

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

3. Final Answer:

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

4. Quick Check:

   Boundaries = max single book to total pages [OK]

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

Common Mistakes:

• Setting low to 0 which is invalid
• Setting high less than sum of pages
• Confusing number of students with page boundaries

3. Given books with pages [10, 20, 30, 40] and 2 students, what is the minimum maximum pages allocated per student?

medium

A. 40

B. 70

C. 50

D. 60

Solution

1. Step 1: Check possible max pages allocations

   Try max pages = 50: allocation could be [10,20,30] and [40], but first student has 60 pages, which is >50, so invalid.

2. Step 2: Try max pages = 60

   Allocation: [10,20,30] = 60 pages, [40] = 40 pages. Both <= 60, valid allocation.

3. Final Answer:

   60 -> Option D

4. Quick Check:

   Minimum max pages = 60 [OK]

Hint: Try mid values to check feasibility [OK]

Common Mistakes:

• Choosing max single book pages as answer without checking allocation
• Assuming equal split always works
• Not verifying allocation feasibility

4. Identify the bug in this Go code snippet for checking allocation feasibility:

func isPossible(books []int, students int, mid int) bool {
    count := 1
    sum := 0
    for _, pages := range books {
        if pages > mid {
            return false
        }
        sum += pages
        if sum > mid {
            count++
            sum = pages
        }
    }
    return count <= students
}

medium

A. No bug, code is correct

B. count should increment before sum addition

C. sum should reset to 0 instead of pages after count++

D. Function should return true if count >= students

Solution

1. Step 1: Analyze sum reset logic

   When sum exceeds mid, count increments and sum resets to current pages, which is correct to start new allocation.

2. Step 2: Check return condition

   Returns true if count of students needed is less than or equal to available students, which is correct.

3. Final Answer:

   No bug, code is correct -> Option A

4. Quick Check:

   Sum reset and count logic correct [OK]

Hint: Reset sum to current pages after exceeding mid [OK]

Common Mistakes:

• Resetting sum to 0 instead of current pages
• Returning true when count exceeds students
• Incrementing count too early

5. You have books with pages [12, 34, 67, 90] and 2 students. Using binary search on answer, what is the minimum maximum pages allocated? Also, explain why allocating [12, 34] to one student and [67, 90] to another is not optimal.

hard

A. 113; Because max pages is 157 which is more than minimum possible

B. 67; Because 67 is the median of pages

C. 90; Because 90 is the largest single book pages

D. 113; Because max pages is 90 which is less than 113

Solution

1. Step 1: Calculate sum and max single book pages

   Sum = 12+34+67+90 = 203; max single book = 90; low=90, high=203.

2. Step 2: Check allocation with mid = (90+203)/2 = 146

   Try allocation: [12,34,67] = 113 pages, [90] = 90 pages; max = 113 <= 146, feasible.

3. Step 3: Try smaller mid to find minimum max pages

   Try mid=113: allocation same as above, feasible. Try mid=112: allocation fails.

4. Step 4: Explain why [12,34] and [67,90] is not optimal

   Allocation sums: 46 and 157; max is 157 which is greater than minimum max pages 113.

5. Final Answer:

   113; Because max pages is 157 which is more than minimum possible -> Option A

6. Quick Check:

   Minimum max pages = 113; given allocation max = 157 [OK]

Hint: Check allocations sums to find minimal max pages [OK]

Common Mistakes:

• Assuming largest single book pages is answer
• Not verifying allocation sums
• Confusing median with allocation max pages