Allocate Minimum Pages Binary Search on Answer in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Pages Allocation Function

What is the output of the following JavaScript function when called with books = [10, 20, 30, 40] and students = 2?

DSA Javascript

function isPossible(books, students, mid) {
  let requiredStudents = 1;
  let currentSum = 0;
  for (let pages of books) {
    if (pages > mid) return false;
    if (currentSum + pages > mid) {
      requiredStudents++;
      currentSum = pages;
      if (requiredStudents > students) return false;
    } else {
      currentSum += pages;
    }
  }
  return true;
}

function allocateMinimumPages(books, students) {
  let start = 0;
  let end = books.reduce((a, b) => a + b, 0);
  let result = end;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (isPossible(books, students, mid)) {
      result = mid;
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return result;
}

console.log(allocateMinimumPages([10, 20, 30, 40], 2));

A 90

B 70

C 60

D 100

💡 Hint

Think about dividing the books so that the maximum pages assigned to a student is minimized.

The minimum maximum pages a student can get is 60 by dividing books as [10, 20, 30] and [40].

🧠 Conceptual

intermediate

Understanding the Role of Binary Search in Allocation

Why do we use binary search in the Allocate Minimum Pages problem?

A To find the minimum possible maximum pages assigned to a student efficiently

B To find the minimum number of students needed to allocate books

C To sort the books array before allocation

D To find the maximum number of pages in a single book

💡 Hint

Think about searching for a value in a range rather than searching the array itself.

Binary search helps find the smallest maximum pages that can be assigned to any student by searching the range between the largest single book and the sum of all books.

🔧 Debug

advanced

Identify the Bug in Allocation Feasibility Check

What error will occur when running this code snippet for isPossible function with books = [10, 20, 30], students = 2, mid = 25?

DSA Javascript

function isPossible(books, students, mid) {
  let requiredStudents = 1;
  let currentSum = 0;
  for (let pages of books) {
    if (pages > mid) return false;
    if (currentSum + pages > mid) {
      requiredStudents++;
      currentSum = pages;
      if (requiredStudents > students) return false;
    } else {
      currentSum += pages;
    }
  }
  return true;
}

console.log(isPossible([10, 20, 30], 2, 25));

A Infinite loop occurs

B Returns true correctly

C Throws a ReferenceError due to undefined variable

D Returns false incorrectly because of wrong comparison operator

💡 Hint

Check the condition that compares pages with mid.

The condition 'if (pages >= mid)' should be 'if (pages > mid)' because if a book has pages equal to mid, it can still be allocated.

❓ Predict Output

advanced

Output of Allocation with Multiple Students

What is the output of allocateMinimumPages([12, 34, 67, 90], 2)?

DSA Javascript

function isPossible(books, students, mid) {
  let requiredStudents = 1;
  let currentSum = 0;
  for (let pages of books) {
    if (pages > mid) return false;
    if (currentSum + pages > mid) {
      requiredStudents++;
      currentSum = pages;
      if (requiredStudents > students) return false;
    } else {
      currentSum += pages;
    }
  }
  return true;
}

function allocateMinimumPages(books, students) {
  let start = 0;
  let end = books.reduce((a, b) => a + b, 0);
  let result = end;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (isPossible(books, students, mid)) {
      result = mid;
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return result;
}

console.log(allocateMinimumPages([12, 34, 67, 90], 2));

A 124

B 113

C 157

D 90

💡 Hint

Try dividing books into two groups to minimize the maximum pages.

The minimum maximum pages is 113 by dividing as [12, 34, 67] and [90].

🧠 Conceptual

expert

Why is Greedy Check Used in Binary Search for Allocation?

In the Allocate Minimum Pages problem, why do we use a greedy approach inside the binary search feasibility check?

A To verify if a given maximum page limit can be assigned without exceeding student count

B To quickly find the exact minimum pages without searching

C To sort the books in ascending order before allocation

D To calculate the total sum of pages for all books

💡 Hint

Think about how we check if a mid value is valid during binary search.

The greedy check tries to allocate books to students without exceeding the mid value to verify feasibility.

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