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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Pages Allocation for Given Books

What is the output of the following TypeScript code that finds the minimum number of pages allocated to a student using binary search?

DSA Typescript

function isPossible(books: number[], students: number, maxPages: number): boolean {
  let requiredStudents = 1;
  let currentSum = 0;
  for (const pages of books) {
    if (pages > maxPages) return false;
    if (currentSum + pages > maxPages) {
      requiredStudents++;
      currentSum = pages;
      if (requiredStudents > students) return false;
    } else {
      currentSum += pages;
    }
  }
  return true;
}

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

const books = [12, 34, 67, 90];
const students = 2;
console.log(allocateMinimumPages(books, students));

A 113

B 157

C 90

D 67

💡 Hint

Think about how binary search narrows down the maximum pages a student can get while ensuring all books are allocated.

The minimum maximum pages allocated to a student is 113. The books can be divided as [12, 34, 67] and [90], where the maximum pages assigned is 113.

🧠 Conceptual

intermediate

Understanding the Role of Binary Search in Allocate Minimum Pages

Why do we use binary search in the Allocate Minimum Pages problem instead of a linear search?

A Because linear search cannot be used on arrays of numbers.

B Because binary search sorts the array before allocation.

C Because binary search always finds the maximum pages directly without checking feasibility.

D Because binary search efficiently narrows down the minimum maximum pages by checking feasibility in logarithmic time.

💡 Hint

Consider how the search space is reduced when checking if allocation is possible.

Binary search helps find the minimum maximum pages by repeatedly checking if a mid value can be used to allocate books to students. This reduces the search space efficiently.

🔧 Debug

advanced

Identify the Bug in the Allocation Feasibility Check

What error will occur when running this feasibility check function for allocation, and why? function isPossible(books: number[], students: number, maxPages: number): boolean { let requiredStudents = 1; let currentSum = 0; for (const pages of books) { if (pages >= maxPages) return false; if (currentSum + pages > maxPages) { requiredStudents++; currentSum = pages; if (requiredStudents > students) return false; } else { currentSum += pages; } } return true; }

A It always returns true regardless of input.

B It throws a runtime error due to uninitialized variables.

C It returns false incorrectly when a book has pages equal to maxPages, causing wrong allocation.

D It causes an infinite loop.

💡 Hint

Check the condition that compares pages with maxPages carefully.

The condition 'pages >= maxPages' returns false even when a book's pages equal maxPages, but allocation should allow that. It should be 'pages > maxPages'.

❓ Predict Output

advanced

Result of Allocation with Multiple Students and Books

What is the output of the following code snippet?

DSA Typescript

const books = [10, 20, 30, 40, 50];
const students = 3;

function isPossible(books: number[], students: number, maxPages: number): boolean {
  let requiredStudents = 1;
  let currentSum = 0;
  for (const pages of books) {
    if (pages > maxPages) return false;
    if (currentSum + pages > maxPages) {
      requiredStudents++;
      currentSum = pages;
      if (requiredStudents > students) return false;
    } else {
      currentSum += pages;
    }
  }
  return true;
}

function allocateMinimumPages(books: number[], students: number): number {
  let start = Math.max(...books);
  let end = books.reduce((a, b) => a + b, 0);
  let result = end;
  while (start <= end) {
    const 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(books, students));

A 100

B 60

C 90

D 70

💡 Hint

Try dividing books into 3 parts with minimum maximum sum.

The minimum maximum pages is 60, with allocation like [10,20,30], [40], [50].

🧠 Conceptual

expert

Why is Binary Search on Answer Space Optimal for Allocate Minimum Pages?

Explain why binary searching on the answer space (range of possible maximum pages) is more efficient than trying all possible allocations directly.

A Because the answer space is sorted and monotonic, allowing binary search to discard half the possibilities each time, reducing complexity from exponential to logarithmic.

B Because binary search sorts the books first, making allocation easier.

C Because trying all allocations directly is faster but uses more memory.

D Because binary search guarantees the maximum pages will be the sum of all books.

💡 Hint

Think about how feasibility changes as maximum pages allowed increases or decreases.

The feasibility of allocation is monotonic with respect to max pages: if allocation is possible at some max pages, it is possible for any larger max pages. This property allows binary search to efficiently find the minimum max pages.

Practice

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

easy

A. To assign pages randomly among students

B. To maximize the total number of pages assigned

C. To find the average number of pages per student

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

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 D

4. Quick Check:

   Goal = minimize max pages [OK]

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

Common Mistakes:

• Trying to maximize pages instead of minimizing
• Ignoring the maximum pages constraint
• Confusing total pages with max pages per student

2. Which of the following is the correct TypeScript syntax to declare the binary search boundaries for the Allocate Minimum Pages problem given an array pages?

easy

A. let low = pages.length; let high = Math.max(...pages);

B. let low = Math.min(...pages); let high = pages.length;

C. let low = 0; let high = pages.reduce((a, b) => a + b, 0);

D. let low = 0; let high = Math.min(...pages);

Solution

1. Step 1: Determine low and high boundaries

   Low is minimum possible max pages (0 or max single book pages), high is sum of all pages (max total pages).

2. Step 2: Check correct syntax for sum

   Using reduce sums all pages correctly for high boundary.

3. Final Answer:

   let low = 0; let high = pages.reduce((a, b) => a + b, 0); -> Option C

4. Quick Check:

   low = 0, high = sum pages [OK]

Hint: Sum array for high, zero or max page for low [OK]

Common Mistakes:

• Setting low as pages.length instead of page count
• Using min pages as high boundary
• Incorrect sum calculation syntax

3. Consider the following TypeScript code snippet for checking feasibility in Allocate Minimum Pages problem:

function isPossible(pages: number[], students: number, maxPages: number): boolean {
  let requiredStudents = 1;
  let currentSum = 0;
  for (let page of pages) {
    if (page > maxPages) return false;
    if (currentSum + page > maxPages) {
      requiredStudents++;
      currentSum = page;
    } else {
      currentSum += page;
    }
  }
  return requiredStudents <= students;
}

What is the output of isPossible([10, 20, 30, 40], 2, 50)?

medium

A. false

B. SyntaxError

C. true

D. RuntimeError

Solution

1. Step 1: Trace allocation with maxPages = 50

   Assign pages: 10+20=30 (still <=50), add 30 would exceed 50, so new student starts with 30, then 40 exceeds 50 if added, so new student starts with 40.

2. Step 2: Count required students

   We used 3 students but only 2 allowed, so requiredStudents=3 > 2 means return false. But check carefully: 10+20=30, next 30 alone fits in second student, 40 alone needs third student.

3. Final Answer:

   false -> Option A

4. Quick Check:

   Required students = 3 > 2, so false [OK]

Hint: Count students needed, compare with allowed [OK]

Common Mistakes:

• Ignoring that a single book can exceed maxPages
• Miscounting students when sum exceeds maxPages
• Assuming sum of all pages fits in one student

4. The following TypeScript function attempts to find the minimum maximum pages but has a bug. Identify the bug.

function findMinPages(pages: number[], students: number): number {
  let low = Math.min(...pages);
  let high = pages.reduce((a, b) => a + b, 0);
  let result = high;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (isPossible(pages, students, mid)) {
      result = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return result;
}

medium

A. High should be min page, not sum of pages

B. Low should start from max page, not min page

C. Mid calculation causes infinite loop

D. Result variable is not updated

Solution

1. Step 1: Analyze low boundary initialization

   Low should be the maximum single book pages, because no student can get less than the largest book.

2. Step 2: Identify impact of wrong low

   Starting low at minimum page can cause incorrect feasibility checks and longer search.

3. Final Answer:

   Low should start from max page, not min page -> Option B

4. Quick Check:

   Low = max page [OK]

Hint: Low boundary = max single book pages [OK]

Common Mistakes:

• Setting low to min page instead of max page
• Confusing high boundary with low
• Not updating result inside loop

5. Given books with pages [12, 34, 67, 90] and 3 students, what is the minimum maximum pages allocated to any student using binary search on answer?

hard

A. 90

B. 113

C. 67

D. 34

Solution

1. Step 1: Set search boundaries

   Low = max pages = 90, High = sum pages = 12+34+67+90=203.

2. Step 2: Binary search feasibility checks

   Mid = (90+203)//2=146. Check if possible with maxPages=146: allocate [12+34+67=113] to student1, 90 to student2, only 2 students needed <=3, possible. So high=145.

3. Step 3: Narrow down to minimum max pages

   Continuing: mid=103 possible [12+34=46,67,90] 3 students. mid=96 possible. mid=92 possible. mid=90: [12+34=46], [67], [90] all <=90, 3 students <=3 feasible, high=89. Loop ends with result=90.

4. Step 4: Re-evaluate minimum max pages

   Check if 113 is feasible with 3 students: [12+34+67=113], [90] 2 students needed <=3, so 113 is feasible but not minimum.

5. Step 5: Check if 90 is feasible

   Allocations: [12+34=46], [67], [90] 3 students needed <=3, feasible.

6. Final Answer:

   90 -> Option A

7. Quick Check:

   Minimum max pages = 90 [OK]

Hint: Binary search between max page and sum pages [OK]

Common Mistakes:

• Misallocating at max=90 thinking 4 students needed
• Miscounting students during allocation
• Confusing with 2 students (113)