Binary Search on Answer Technique in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search on Answer for Minimum Maximum Subarray Sum

What is the output of the following JavaScript code that uses binary search on answer to find the minimum largest sum among subarrays?

DSA Javascript

function canSplit(nums, maxSum, m) {
  let currentSum = 0, count = 1;
  for (const num of nums) {
    if (currentSum + num > maxSum) {
      count++;
      currentSum = num;
      if (count > m) return false;
    } else {
      currentSum += num;
    }
  }
  return true;
}

function splitArray(nums, m) {
  let left = Math.max(...nums);
  let right = nums.reduce((a, b) => a + b, 0);
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (canSplit(nums, mid, m)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

const nums = [7,2,5,10,8];
const m = 2;
console.log(splitArray(nums, m));

A 18

B 15

C 20

D 23

💡 Hint

Think about splitting the array into 2 parts such that the largest sum among them is minimized.

The binary search tries sums between max element (10) and total sum (32). The minimum largest sum to split into 2 subarrays is 18.

🧠 Conceptual

intermediate

Understanding Binary Search on Answer Technique

Which of the following best describes the main idea behind the binary search on answer technique?

A Perform binary search on the input array elements directly to find a target value.

B Use binary search on a range of possible answers to find the minimum or maximum feasible value satisfying a condition.

C Sort the array and then apply binary search to find the median element.

D Use binary search to find the first occurrence of a value in a sorted array.

💡 Hint

Think about searching over a range of values, not array indices.

Binary search on answer searches over a range of possible answers, checking feasibility at each step to narrow down the answer.

🔧 Debug

advanced

Identify the Error in Binary Search on Answer Implementation

What error does the following code produce when trying to find the minimum maximum subarray sum using binary search on answer?

DSA Javascript

function canSplit(nums, maxSum, m) {
  let currentSum = 0, count = 1;
  for (const num of nums) {
    if (currentSum + num >= maxSum) {
      count++;
      currentSum = num;
      if (count > m) return false;
    } else {
      currentSum += num;
    }
  }
  return true;
}

function splitArray(nums, m) {
  let left = Math.max(...nums);
  let right = nums.reduce((a, b) => a + b, 0);
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (canSplit(nums, mid, m)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

const nums = [7,2,5,10,8];
const m = 2;
console.log(splitArray(nums, m));

A The function does not handle empty arrays, causing runtime error.

B The initial left boundary should be 0 instead of max element.

C The condition 'currentSum + num >= maxSum' causes incorrect splitting, leading to wrong output.

D The binary search loop condition should be 'left <= right' instead of 'left < right'.

💡 Hint

Check the condition that triggers a new subarray split.

Using '>=' causes splitting even when sum equals maxSum, which is incorrect and leads to more splits than needed.

🚀 Application

advanced

Applying Binary Search on Answer to Allocate Books Problem

Given an array representing pages in books and number of students, which output is correct for minimum maximum pages allocated using binary search on answer?

DSA Javascript

function isPossible(books, maxPages, students) {
  let requiredStudents = 1, 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 allocateBooks(books, students) {
  let left = Math.max(...books);
  let right = books.reduce((a, b) => a + b, 0);
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (isPossible(books, mid, students)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

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

A 113

B 157

C 67

D 90

💡 Hint

Try splitting books into 2 students with minimum maximum pages.

Splitting as [12,34,67] and [90] gives max pages 113, which is minimum possible.

🧠 Conceptual

expert

Why is Binary Search on Answer Efficient for Certain Problems?

Why does binary search on answer technique provide an efficient solution for problems like splitting arrays or allocating resources?

A Because it uses dynamic programming to store intermediate results.

B Because it sorts the input data first, reducing complexity.

C Because it uses recursion to explore all possible partitions quickly.

D Because it converts a complex problem into a series of feasibility checks over a numeric range, reducing search space logarithmically.

💡 Hint

Think about how the search space is reduced step by step.

Binary search on answer reduces the problem to checking feasibility for mid values, cutting search space in half each time.