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.