Allocate Minimum Pages Binary Search on Answer in DSA Javascript

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 it works, then adjust the guess using binary search.

Analogy: Imagine you have a stack of books and a few friends. You want to give books to friends so that no one gets too many pages to read. You try a limit on pages per friend and see if you can split the books without breaking the limit. If yes, try smaller limit; if no, try bigger limit.

Books: [100] -> [200] -> [300] -> [400] -> null
Students: 2
Trying max pages limit: 500
Split: [100, 200] -> [300, 400] -> null

Dry Run Walkthrough

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

Goal: Find the minimum maximum pages assigned to any student 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; maximum is sum of all pages

Step 2: Calculate mid = (400 + 1000) / 2 = 700; check if possible to allocate with max 700 pages

Trying max_pages=700

Why: Check feasibility with mid value to narrow search

Step 3: Allocate books: Student 1 gets 100 + 200 + 300 = 600 pages; Student 2 gets 400 pages

Allocation possible with max_pages=700

Why: Sum per student does not exceed 700, so allocation is possible

Step 4: Since allocation possible, set high = mid - 1 = 699 to try smaller max pages

low=400, high=699

Why: Try to find smaller maximum pages

Step 5: Calculate mid = (400 + 699) / 2 = 549; check allocation with max 549

Trying max_pages=549

Why: Narrow search further

Step 6: Allocate books: Student 1 gets 100 + 200 = 300 pages; Student 2 gets 300 pages; next book 400 pages can't fit in max 549 for any student

Allocation not possible with max_pages=549

Why: 400 pages book alone exceeds remaining capacity for student 2

Step 7: Since allocation not possible, set low = mid + 1 = 550

low=550, high=699

Why: Need larger max pages to fit all books

Step 8: Calculate mid = (550 + 699) / 2 = 624; check allocation with max 624

Trying max_pages=624

Why: Try mid value again

Step 9: Allocate books: Student 1 gets 100 + 200 + 300 = 600 pages; Student 2 gets 400 pages

Allocation possible with max_pages=624

Why: Sum per student does not exceed 624

Step 10: Set high = mid - 1 = 623 to try smaller max pages

low=550, high=623

Why: Try to minimize max pages further

Step 11: Calculate mid = (550 + 623) / 2 = 586; check allocation with max 586

Trying max_pages=586

Why: Narrow search

Step 12: Allocation not possible (same reason as step 6)

Allocation not possible with max_pages=586

Why: 400 pages book can't fit after previous allocations

Step 13: Set low = mid + 1 = 587

low=587, high=623

Why: Increase minimum max pages

Step 14: Calculate mid = (587 + 623) / 2 = 605; check allocation with max 605

Trying max_pages=605

Why: Try mid value

Step 15: Allocation possible: Student 1 gets 100 + 200 + 300 = 600 pages; Student 2 gets 400 pages

Allocation possible with max_pages=605

Why: Sum per student within limit

Step 16: Set high = mid - 1 = 604

low=587, high=604

Why: Try smaller max pages

Step 17: Calculate mid = (587 + 604) / 2 = 595; check allocation with max 595

Trying max_pages=595

Why: Narrow search

Step 18: Allocation not possible (same reason as step 6)

Allocation not possible with max_pages=595

Why: 400 pages book can't fit

Step 19: Set low = mid + 1 = 596

low=596, high=604

Why: Increase minimum max pages

Step 20: Calculate mid = (596 + 604) / 2 = 600; check allocation with max 600

Trying max_pages=600

Why: Try mid value

Step 21: Allocation possible: Student 1 gets 100 + 200 + 300 = 600 pages; Student 2 gets 400 pages

Allocation possible with max_pages=600

Why: Sum per student within limit

Step 22: Set high = mid - 1 = 599

low=596, high=599

Why: Try smaller max pages

Step 23: Calculate mid = (596 + 599) / 2 = 597; check allocation with max 597

Trying max_pages=597

Why: Narrow search

Step 24: Allocation not possible (same reason as step 6)

Allocation not possible with max_pages=597

Why: 400 pages book can't fit

Step 25: Set low = mid + 1 = 598

low=598, high=599

Why: Increase minimum max pages

Step 26: Calculate mid = (598 + 599) / 2 = 598; check allocation with max 598

Trying max_pages=598

Why: Try mid value

Step 27: Allocation not possible (same reason as step 6)

Allocation not possible with max_pages=598

Why: 400 pages book can't fit

Step 28: Set low = mid + 1 = 599

low=599, high=599

Why: Increase minimum max pages

Step 29: Calculate mid = (599 + 599) / 2 = 599; check allocation with max 599

Trying max_pages=599

Why: Try mid value

Step 30: Allocation not possible (same reason as step 6)

Allocation not possible with max_pages=599

Why: 400 pages book can't fit

Step 31: Set low = mid + 1 = 600

low=600, high=599

Why: low > high means search ends

Result:

Minimum maximum pages = 600
Final allocation: Student 1: [100, 200, 300], Student 2: [400]

Annotated Code

DSA Javascript

class BookAllocator {
  constructor(books, students) {
    this.books = books;
    this.students = students;
  }

  // Check if allocation possible with maxPages limit
  canAllocate(maxPages) {
    let requiredStudents = 1;
    let currentSum = 0;

    for (const pages of this.books) {
      if (pages > maxPages) return false; // single book exceeds limit

      if (currentSum + pages > maxPages) {
        requiredStudents++;
        currentSum = pages;
        if (requiredStudents > this.students) return false; // need more students
      } else {
        currentSum += pages;
      }
    }
    return true;
  }

  // Binary search to find minimum max pages
  findMinPages() {
    let low = Math.max(...this.books);
    let high = this.books.reduce((a, b) => a + b, 0);
    let result = high;

    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      if (this.canAllocate(mid)) {
        result = mid; // possible to allocate with mid
        high = mid - 1; // try smaller max pages
      } else {
        low = mid + 1; // need bigger max pages
      }
    }
    return result;
  }
}

// Driver code
const books = [100, 200, 300, 400];
const students = 2;
const allocator = new BookAllocator(books, students);
const minPages = allocator.findMinPages();
console.log(minPages + '');

if (pages > maxPages) return false; // single book exceeds limit

Check if any single book is larger than maxPages, making allocation impossible

if (currentSum + pages > maxPages) { requiredStudents++; currentSum = pages; if (requiredStudents > this.students) return false; }

Start new student allocation if current sum exceeds maxPages; fail if students needed exceed available

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

Binary search to find minimum maxPages that allows allocation

Output

600

Complexity Analysis

Time: O(n log S) because we do binary search on the sum of pages S, and each check scans all n books

Space: O(n) for storing the books array

vs Alternative: Naive approach tries all possible max pages from max book to sum, which is O(n * S) and much slower

Edge Cases

Only one book

Minimum max pages is the pages of that single book

DSA Javascript

if (pages > maxPages) return false;

Number of students equals number of books

Minimum max pages is the largest single book pages

DSA Javascript

if (pages > maxPages) return false;

Number of students is 1

Minimum max pages is sum of all book pages

DSA Javascript

let high = this.books.reduce((a, b) => a + b, 0);

When to Use This Pattern

When you need to split an array into k parts minimizing the maximum sum of parts, use binary search on the answer to efficiently find the optimal maximum sum.

Common Mistakes

Mistake: Not checking if a single book exceeds the current maxPages guess, causing wrong allocation results
Fix: Add a check to immediately return false if any single book has pages greater than maxPages

Mistake: Updating low and high incorrectly in binary search, causing infinite loops or wrong answers
Fix: Update high = mid - 1 when allocation possible, low = mid + 1 when not possible

Summary

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

Use it when you want to split work or load evenly minimizing the maximum load.

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

Practice

1. What is the main goal of the Allocate Minimum Pages problem when using binary search on the 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 student with the least pages

D. To sort the pages in ascending order

Solution

1. Step 1: Understand the problem goal

   The problem aims to divide books 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 on the maximum pages assigned to any student to find the minimum possible maximum.

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 sorting with allocation
• Assuming equal pages per student

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

easy

A. let low = 0, high = sum of all pages;

B. let low = max pages in a single book, high = sum of all pages;

C. let low = 0, high = max pages in a single book;

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

Solution

1. Step 1: Determine low boundary

   Low should be at least the maximum pages in a single book because no student can get less than that.

2. Step 2: Determine high boundary

   High is the sum of all pages, representing the case where one student reads all books.

3. Final Answer:

   let low = max pages in a single book, high = sum of all pages; -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Setting low to 0 which is too low
• Swapping low and high values
• Using arbitrary boundaries

3. Given books with pages [10, 20, 30, 40] and 2 students, what is the minimum maximum pages assigned to a student using binary search on answer?

medium

A. 40

B. 50

C. 60

D. 70

Solution

1. Step 1: Calculate boundaries

   Max single book pages = 40, sum = 100. So low=40, high=100.

2. Step 2: Apply binary search and check feasibility

   Mid = 70: Can we allocate so max pages ≤ 70? Yes: [10,20,30] and [40]. Try lower mid.

3. Step 3: Check mid = 55

   Allocate: [10,20,30] sum=60 > 55, so no. Increase low to 56.

4. Step 4: Check mid = 60

   Allocate: [10,20,30] sum=60 ≤ 60, [40] next. Possible, try lower.

5. Step 5: Check mid = 50

   Allocate: [10,20] sum=30 ≤ 50, next [30,40] sum=70 > 50 no. So 50 not possible.

6. Final Answer:

   60 -> Option C

7. Quick Check:

   Minimum max pages = 60 [OK]

Hint: Check mid feasibility by simulating allocation [OK]

Common Mistakes:

• Choosing sum/2 without checking feasibility
• Ignoring max single book pages
• Misallocating books to students

4. Identify the bug in this JavaScript snippet for checking feasibility in Allocate Minimum Pages problem:

function isPossible(books, students, maxPages) {
  let count = 1, sum = 0;
  for (let i = 0; i < books.length; i++) {
    sum += books[i];
    if (sum > maxPages) {
      count++;
      sum = books[i];
    }
  }
  return count <= students;
}

medium

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

B. It does not reset sum correctly after exceeding maxPages

C. It increments count even when sum equals maxPages

D. It uses a for loop instead of while loop

Solution

1. Step 1: Analyze sum accumulation

   The code adds book pages to sum and resets sum when sum > maxPages, increasing count.

2. Step 2: Check for single book pages exceeding maxPages

   There is no check if any single book's pages exceed maxPages, which makes allocation impossible.

3. Final Answer:

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

4. Quick Check:

   Missing single book page check [OK]

Hint: Always check single book pages ≤ maxPages first [OK]

Common Mistakes:

• Ignoring single book page size check
• Resetting sum incorrectly
• Confusing loop types

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? Also, explain why allocating [12, 34, 67] to one student and [90] to another is optimal.

hard

A. Minimum max pages is 101; allocation is not optimal because 67+34=101 < 113

B. Minimum max pages is 90; allocation is optimal

C. Minimum max pages is 113; allocation is not optimal because 12+34+67=113 is too high

D. Minimum max pages is 113; allocation is optimal

Solution

1. Step 1: Calculate boundaries and try allocations

   Max single book = 90, sum = 203. Low=90, High=203.

2. Step 2: Check mid = 146

   Allocate: [12,34,67] sum=113 ≤146, [90] sum=90 ≤146. Possible, try lower.

3. Step 3: Check mid = 113

   Allocate: [12,34,67] sum=113 ≤113, [90] sum=90 ≤113. Possible, try lower.

4. Step 4: Check mid = 101

   Allocate: [12,34,67] sum=113 >101 no. Try [12,34] sum=46 ≤101, next [67,90] sum=157 >101 no. Not possible.

5. Step 5: Conclusion

   Minimum max pages = 113. Allocation [12,34,67] and [90] achieves max(113,90)=113, which is the minimum possible maximum, so it is optimal.

6. Final Answer:

   Minimum max pages is 113; allocation is optimal -> Option D

7. Quick Check:

   Minimum max pages = 113, allocation optimal [OK]

Hint: Try mid values and simulate allocation carefully [OK]

Common Mistakes:

• Assuming 90 is minimum max pages
• Ignoring sum of allocated books
• Not testing all allocation splits