Allocate Minimum Pages Binary Search on Answer in DSA Javascript - Build from Scratch

Allocate Minimum Pages using Binary Search on Answer

📖 Scenario: You are a librarian who needs to allocate books to students. Each book has a certain number of pages. You want to distribute the books so that the student who reads the most pages reads as few pages as possible.This helps keep the reading load balanced and fair.

🎯 Goal: Build a program that finds the minimum possible maximum number of pages assigned to any student using binary search on the answer.

📋 What You'll Learn

Create an array called books with the exact values [12, 34, 67, 90]

Create a variable called students and set it to 2

Write a function called isPossible that takes books, students, and mid as parameters and returns true if allocation is possible with max pages mid, otherwise false

Use binary search with variables start, end, and result to find the minimum maximum pages

Print the final result which is the minimum maximum pages any student has to read

💡 Why This Matters

🌍 Real World

This technique helps in dividing workloads fairly, like assigning tasks or resources evenly among people.

💼 Career

Binary search on answer is a common pattern in coding interviews and helps solve optimization problems efficiently.

1

Create the books array

Create an array called books with these exact values: [12, 34, 67, 90]

DSA Javascript

# Create the array books with the given values
# Your code here

Hint

Use const books = [12, 34, 67, 90]; to create the array.

2

Set the number of students

Create a variable called students and set it to 2

DSA Javascript

const books = [12, 34, 67, 90];
# Create the variable students and set it to 2
# Your code here

Hint

Use const students = 2; to set the number of students.

3

Write the isPossible function

Write a function called isPossible that takes books, students, and mid as parameters. It should return true if it is possible to allocate books so that no student reads more than mid pages, otherwise false. Use a loop to sum pages and count students needed.

DSA Javascript

const books = [12, 34, 67, 90];
const students = 2;
// Write the isPossible function below
# Your code here

Hint

Loop through books, add pages to a sum. If sum exceeds mid, assign to next student. If students needed exceed students, return false.

4

Use binary search to find minimum maximum pages and print result

Use binary search with variables start, end, and result to find the minimum maximum pages any student has to read. Print the result.

DSA Javascript

const books = [12, 34, 67, 90];
const students = 2;

function isPossible(books, students, mid) {
    let studentCount = 1;
    let pagesSum = 0;
    for (let i = 0; i  mid) {
            return false;
        }
        if (pagesSum + books[i] > mid) {
            studentCount++;
            pagesSum = books[i];
            if (studentCount > students) {
                return false;
            }
        } else {
            pagesSum += books[i];
        }
    }
    return true;
}

// Use binary search to find minimum maximum pages and print result
# Your code here

Hint

Use binary search between 0 and sum of all pages. Use isPossible to check mid. Adjust start and end accordingly. Print final result.

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