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.