Allocate Minimum Pages Binary Search on Answer in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the maximum number of pages in the books array.

DSA Typescript

function maxPages(books: number[]): number {
  let max = 0;
  for (let i = 0; i < books.length; i++) {
    if (books[i] [1] max) {
      max = books[i];
    }
  }
  return max;
}

Drag options to blanks, or click blank then click option'

A!=

B<

C==

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' causes max to stay at 0.

Using '==' or '!=' does not update max correctly.

We compare each book's pages to the current max and update max if the current book has more pages.

2fill in blank

medium

Complete the code to check if it is possible to allocate books such that no student reads more than maxPages.

DSA Typescript

function isPossible(books: number[], students: number, maxPages: number): boolean {
  let studentCount = 1;
  let currentSum = 0;
  for (let i = 0; i < books.length; i++) {
    if (currentSum + books[i] > [1]) {
      studentCount++;
      currentSum = books[i];
      if (studentCount > students) {
        return false;
      }
    } else {
      currentSum += books[i];
    }
  }
  return true;
}

Drag options to blanks, or click blank then click option'

Astudents

BmaxPages

Cbooks.length

DcurrentSum

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with students or books.length instead of maxPages.

Not resetting currentSum when allocating to a new student.

We check if adding the current book exceeds maxPages, then allocate to next student.

3fill in blank

hard

Fix the error in the binary search loop condition to correctly find the minimum maximum pages.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

A<=

B>=

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>=' or '>' causes the loop to never run or run incorrectly.

Using '<=' can cause off-by-one errors.

The binary search should continue while start is less than end to avoid infinite loop.

4fill in blank

hard

Fill both blanks to correctly initialize the binary search boundaries for allocating minimum pages.

DSA Typescript

function allocatePages(books: number[], students: number): number {
  let start = [1];
  let end = [2];
  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;
}

Drag options to blanks, or click blank then click option'

AMath.max(...books)

B0

Cbooks.length

Dbooks.reduce((a, b) => a + b, 0)

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from 0 causes incorrect lower bound.

Using books.length as boundary is incorrect.

Start with the largest single book pages and end with the sum of all pages.

5fill in blank

hard

Fill all three blanks to complete the function that allocates minimum pages using binary search and helper function.

DSA Typescript

function allocateMinPages(books: number[], students: number): number {
  let start = [1];
  let end = [2];
  let result = end;
  while (start < end) {
    let mid = Math.floor((start + end) / 2);
    if ([3](books, students, mid)) {
      result = mid;
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return result;
}

Drag options to blanks, or click blank then click option'

AMath.max(...books)

Bbooks.reduce((a, b) => a + b, 0)

CisPossible

Dstudents

Attempts:

3 left

💡 Hint

Common Mistakes

Using students as a boundary instead of sum of pages.

Calling a wrong function instead of isPossible.

Initialize start and end correctly and call isPossible to check feasibility.