Binary Search on Answer Technique in DSA Java - 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 Java code that uses binary search on answer to find the minimum largest sum among subarrays?

DSA Java

public class Solution {
    public static boolean canSplit(int[] nums, int m, int maxSum) {
        int currentSum = 0, count = 1;
        for (int num : nums) {
            if (currentSum + num > maxSum) {
                count++;
                currentSum = num;
                if (count > m) return false;
            } else {
                currentSum += num;
            }
        }
        return true;
    }

    public static int splitArray(int[] nums, int m) {
        int left = 0, right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canSplit(nums, m, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {7, 2, 5, 10, 8};
        int m = 2;
        System.out.println(splitArray(nums, m));
    }
}

A 18

B 15

C 20

D 25

💡 Hint

Think about how the array can be split into 2 subarrays with minimum largest sum.

The array can be split as [7,2,5] and [10,8] with sums 14 and 18. The minimum largest sum possible is 18.

🧠 Conceptual

intermediate

Understanding the Role of the 'canSplit' Function

In the binary search on answer technique, what is the main purpose of the 'canSplit' function in the context of splitting an array into subarrays?

A To sort the array before applying binary search

B To find the maximum sum of all subarrays after splitting

C To check if the array can be split into at most m subarrays with each subarray sum less than or equal to a given maxSum

D To calculate the total sum of the array elements

💡 Hint

Think about the condition that guides the binary search direction.

The 'canSplit' function verifies if a candidate maxSum allows splitting the array into m or fewer subarrays without exceeding maxSum in any subarray.

❓ Predict Output

advanced

Output of Binary Search on Answer for Minimum Time to Complete Jobs

What is the output of the following Java code that uses binary search on answer to find the minimum time to complete all jobs by workers?

DSA Java

public class Solution {
    public static boolean canFinish(int[] jobs, int workers, int maxTime) {
        int count = 1, currentTime = 0;
        for (int job : jobs) {
            if (job > maxTime) return false;
            if (currentTime + job > maxTime) {
                count++;
                currentTime = job;
                if (count > workers) return false;
            } else {
                currentTime += job;
            }
        }
        return true;
    }

    public static int minTime(int[] jobs, int workers) {
        int left = 0, right = 0;
        for (int job : jobs) right += job;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFinish(jobs, workers, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] jobs = {3, 2, 3};
        int workers = 3;
        System.out.println(minTime(jobs, workers));
    }
}

A 4

B 3

C 5

D 6

💡 Hint

Each worker can do one job, so minimum time is the longest single job time.

With 3 workers and jobs [3,2,3], each worker can do one job. The minimum time is max job time 3.

🔧 Debug

advanced

Identify the Error in Binary Search on Answer Implementation

What error will the following Java code produce when run, and why?

DSA Java

public class Solution {
    public static boolean canSplit(int[] nums, int m, int maxSum) {
        int currentSum = 0, count = 1;
        for (int num : nums) {
            if (currentSum + num >= maxSum) {
                count++;
                currentSum = num;
                if (count > m) return false;
            } else {
                currentSum += num;
            }
        }
        return true;
    }

    public static int splitArray(int[] nums, int m) {
        int left = 0, right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canSplit(nums, m, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {7, 2, 5, 10, 8};
        int m = 2;
        System.out.println(splitArray(nums, m));
    }
}

A The code throws NullPointerException because nums is not initialized

B The code throws ArrayIndexOutOfBoundsException due to incorrect loop indexing

C The code outputs 18, which is correct

D The code outputs 17, which is incorrect because the condition uses '>=' instead of '>' causing premature splits

💡 Hint

Check the condition that triggers a new subarray split.

Using '>=' causes splitting even when sum equals maxSum, leading to more splits and a smaller max sum than correct.

🚀 Application

expert

Minimum Capacity to Ship Packages Within D Days

Given weights of packages and days D, binary search on answer is used to find the minimum ship capacity to ship all packages within D days. If weights = [1,2,3,4,5,6,7,8,9,10] and D = 5, what is the minimum capacity?

A 15

B 18

C 20

D 22

💡 Hint

Try to split the packages into 5 days with minimum max daily weight.

The minimum capacity is 15, allowing splits like [1,2,3,4,5], [6,7], [8], [9], [10].

Practice

1. What is the main idea behind the Binary Search on Answer technique?

easy

A. We guess an answer and check if it satisfies the problem constraints, then adjust the guess.

B. We sort the array and then apply binary search to find an element.

C. We use binary search to find the maximum element in an unsorted array.

D. We divide the array into two halves and solve each half separately.

Solution

1. Step 1: Understand the technique's approach

   Binary Search on Answer guesses a possible answer and checks if it meets the problem's conditions.

2. Step 2: Adjust guess based on check

   If the guess is valid, we try smaller or larger guesses accordingly to find the best answer.

3. Final Answer:

   We guess an answer and check if it satisfies the problem constraints, then adjust the guess. -> Option A

4. Quick Check:

   Guess and check approach = We guess an answer and check if it satisfies the problem constraints, then adjust the guess. [OK]

Hint: Guess answer, check condition, adjust guess accordingly [OK]

Common Mistakes:

• Confusing with normal binary search on sorted arrays
• Thinking it only finds elements, not answers
• Assuming it divides data instead of answer range

2. Which of the following is the correct way to initialize the search range for binary search on answer when finding minimum maximum load among workers?

easy

A. low = 0; high = maximum single load

B. low = minimum load; high = maximum load

C. low = 0; high = sum of all loads

D. low = average load; high = sum of all loads

Solution

1. Step 1: Define search range for answer

   Minimum maximum load can be between 0 and sum of all loads because no worker can have load more than total.

2. Step 2: Set low and high accordingly

   Set low = 0 and high = sum of all loads to cover all possible answers.

3. Final Answer:

   low = 0; high = sum of all loads -> Option C

4. Quick Check:

   Search range covers all loads = low = 0; high = sum of all loads [OK]

Hint: Set low to minimum possible, high to maximum possible answer [OK]

Common Mistakes:

• Setting low to minimum load instead of 0
• Setting high to max single load instead of sum
• Using average load as boundary

3. Consider the following Java code snippet using binary search on answer to find minimum maximum pages assigned to students:

int[] pages = {10, 20, 30, 40};
int low = 40, high = 100;
while (low < high) {
  int mid = (low + high) / 2;
  if (canAllocate(pages, mid, 2)) {
    high = mid;
  } else {
    low = mid + 1;
  }
}
System.out.println(low);

// canAllocate checks if pages can be divided among 2 students with max pages mid

What will be the output?

medium

A. 70

B. 60

C. 90

D. 100

Solution

1. Step 1: Understand the problem and initial range

   Pages array is {10,20,30,40}, low=40 (max single), high=100 (sum). We want minimum max pages for 2 students.

2. Step 2: Trace binary search iterations

   Mid = 70: canAllocate true (10+20+30=60 <=70 for 1st student, 40 for 2nd). So high=70.
   Mid = 55: canAllocate false (10+20+30=60 >55). So low=56.
   Mid = 63: canAllocate true (10+20+30=60 <=63, 40 for 2nd). high=63.
   Mid = 59: canAllocate false (60 >59). low=60.
   Mid = 61: canAllocate true. high=61.
   Mid = 60: canAllocate true. high=60.
   Mid = 60 again, low=60, high=60 ends loop.

3. Final Answer:

   60 -> Option B

4. Quick Check:

   Minimum max pages = 60 [OK]

Hint: Check mid feasibility, adjust low/high until low meets high [OK]

Common Mistakes:

• Not updating low/high correctly after canAllocate
• Misunderstanding canAllocate logic
• Incorrect mid calculation or loop condition

4. The following code attempts to find the minimum largest sum of subarrays using binary search on answer. Identify the bug:

int[] nums = {7, 2, 5, 10, 8};
int m = 2;
int low = 0, high = 32;
while (low <= high) {
  int mid = (low + high) / 2;
  if (canSplit(nums, mid, m)) {
    high = mid - 1;
  } else {
    low = mid + 1;
  }
}
System.out.println(low);

// canSplit checks if nums can be split into m subarrays with max sum <= mid

medium

A. The initial low should be max element, not 0

B. The loop condition should be low < high, not low <= high

C. The mid calculation should use (low + high + 1) / 2

D. The canSplit function should return false when sum equals mid

Solution

1. Step 1: Check initial low value

   Low is set to 0, but minimum largest sum can't be less than max element (10).

2. Step 2: Correct low initialization

   Set low = max element (10) to ensure valid search range and avoid infinite loop or wrong answer.

3. Final Answer:

   The initial low should be max element, not 0 -> Option A

4. Quick Check:

   Low must start at max element [OK]

Hint: Start low at max element to avoid invalid guesses [OK]

Common Mistakes:

• Starting low at 0 causing invalid mid values
• Using wrong loop condition causing infinite loop
• Misunderstanding canSplit return values

5. You want to find the minimum time required to complete all jobs by k workers, where each job takes a certain time. Using binary search on answer, which approach correctly finds the answer? int[] jobs = {3, 6, 7, 11}; int k = 2; Options:

hard

A. Sort jobs ascending; assign jobs alternately to workers; return max load.

B. Set low = 0, high = max job time; assign jobs greedily without checking mid; return high.

C. Set low = sum of all jobs, high = max job time; use binary search to find minimum sum.

D. Set low = max job time, high = sum of all jobs; check if jobs can be assigned within mid time using k workers; adjust low/high accordingly.

Solution

1. Step 1: Define search boundaries

   Low should be max job time (11), high sum of all jobs (3+6+7+11=27) to cover all possible times.

2. Step 2: Use binary search with feasibility check

   Check if jobs can be assigned to k=2 workers within mid time. Adjust low/high based on feasibility.

3. Final Answer:

   Set low = max job time, high = sum of all jobs; check if jobs can be assigned within mid time using k workers; adjust low/high accordingly. -> Option D

4. Quick Check:

   Binary search on answer with feasibility check = Set low = max job time, high = sum of all jobs; check if jobs can be assigned within mid time using k workers; adjust low/high accordingly. [OK]

Hint: Set low=max job, high=sum; check feasibility; adjust range [OK]

Common Mistakes:

• Setting wrong low/high boundaries
• Not checking feasibility properly
• Assigning jobs without binary search