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

DSA Python

def can_split(nums, max_sum, m):
    current_sum = 0
    count = 1
    for num in nums:
        if current_sum + num > max_sum:
            count += 1
            current_sum = num
            if count > m:
                return False
        else:
            current_sum += num
    return True

def split_array(nums, m):
    left, right = max(nums), sum(nums)
    while left < right:
        mid = (left + right) // 2
        if can_split(nums, mid, m):
            right = mid
        else:
            left = mid + 1
    return left

nums = [7,2,5,10,8]
m = 2
print(split_array(nums, m))

A 17

B 18

C 20

D 15

💡 Hint

Think about how the binary search narrows down the maximum allowed subarray sum.

The code finds the smallest maximum sum possible when splitting the array into 2 subarrays. The answer is 18 because splitting as [7,2,5], [10,8] gives max sums 14 and 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 Using binary search to find the correct value of an answer by checking feasibility within a range.

B Sorting the input array and then applying binary search to find an element.

C Using binary search to find the maximum element in a sorted array.

D Applying binary search to reduce the time complexity of searching in a linked list.

💡 Hint

Think about how binary search is used on a range of possible answers, not on the input data directly.

Binary search on answer works by guessing an answer in a range and checking if it is possible (feasible). Based on feasibility, it narrows the range until the correct answer is found.

🔧 Debug

advanced

Find the error in binary search on answer implementation

What error does the following code raise when trying to find the minimum maximum load for workers?

DSA Python

def can_distribute(weights, max_load, workers):
    current_load = 0
    count = 1
    for w in weights:
        if w > max_load:
            return False
        if current_load + w <= max_load:
            current_load += w
        else:
            count += 1
            current_load = w
    return count <= workers

def min_load(weights, workers):
    left, right = 0, sum(weights)
    while left < right:
        mid = (left + right) // 2
        if can_distribute(weights, mid, workers):
            right = mid
        else:
            left = mid + 1
    return left

weights = [10, 20, 30, 40]
workers = 2
print(min_load(weights, workers))

A Infinite loop because left never increases

B Output is 50 but should be 60

C TypeError due to wrong comparison in can_distribute

D No error; output is 60

💡 Hint

Check the initial values of left and right and how mid is calculated.

The code correctly implements binary search on answer. The minimal maximum load is 60 by splitting as [10,20,30] and [40]. No error occurs.

❓ Predict Output

advanced

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

What is the output of this code that finds the minimum time to finish all jobs by k workers using binary search on answer?

DSA Python

def can_finish(jobs, time_limit, k):
    workers = 1
    current_time = 0
    for job in jobs:
        if job > time_limit:
            return False
        if current_time + job <= time_limit:
            current_time += job
        else:
            workers += 1
            current_time = job
            if workers > k:
                return False
    return True

def min_time(jobs, k):
    left, right = max(jobs), sum(jobs)
    while left < right:
        mid = (left + right) // 2
        if can_finish(jobs, mid, k):
            right = mid
        else:
            left = mid + 1
    return left

jobs = [3, 6, 8, 11]
k = 2
print(min_time(jobs, k))

A 14

B 18

C 17

D 20

💡 Hint

Consider how jobs are assigned to workers to keep total time under mid.

The minimal time is 17 by splitting jobs as [3,6,8] and [11].

🚀 Application

expert

Using Binary Search on Answer to Find Maximum Minimum Distance

You want to place 3 routers in houses located at positions [1, 2, 8, 4, 9]. Using binary search on answer, what is the maximum minimum distance between any two routers?

A 3

B 6

C 5

D 4

💡 Hint

Sort the house positions and check feasibility of placing routers with given minimum distance.

Sorted positions: [1,2,4,8,9]. Maximum minimum distance is 3 by placing routers at positions 1, 4, and 8.

Practice

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

easy

A. We apply binary search to split the input into two equal halves repeatedly.

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

C. We guess an answer and check if it satisfies the problem, then adjust the guess using binary search.

D. We use binary search to find the middle element of a sorted list.

Solution

1. Step 1: Understand the technique's purpose

   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 using binary search to find the optimal answer.

3. Final Answer:

   We guess an answer and check if it satisfies the problem, then adjust the guess using binary search. -> Option C

4. Quick Check:

   Guess and check with binary search = We guess an answer and check if it satisfies the problem, then adjust the guess using binary search. [OK]

Hint: Think of guessing answers and narrowing down with binary search [OK]

Common Mistakes:

• Confusing with normal binary search on sorted arrays
• Thinking it only finds elements, not answers
• Ignoring the check step after guessing

2. Which of the following is the correct syntax to start a binary search on answer in Python for an integer answer between low and high?

easy

A. while low <= high:
mid = (low + high) // 2

B. for mid in range(low, high):

C. if low < high:
mid = (low + high) / 2

D. while low < high:
mid = (low + high) // 2 + 1

Solution

1. Step 1: Identify the binary search loop condition

   Binary search typically uses a while loop with condition low <= high to cover all possible values.

2. Step 2: Calculate mid correctly

   Mid is calculated as integer division (low + high) // 2 to get the middle integer index or value.

3. Final Answer:

   while low <= high: mid = (low + high) // 2 -> Option A

4. Quick Check:

   Correct loop and mid calculation = while low <= high: mid = (low + high) // 2 [OK]

Hint: Use while low <= high and integer division for mid [OK]

Common Mistakes:

• Using for loop instead of while
• Using float division instead of integer division
• Wrong loop condition like low < high

3. Consider the following code snippet using binary search on answer to find the minimum maximum load for splitting an array into m subarrays:

def can_split(nums, m, max_load):
    count, current_sum = 1, 0
    for num in nums:
        if current_sum + num > max_load:
            count += 1
            current_sum = num
            if count > m:
                return False
        else:
            current_sum += num
    return True

nums = [7, 2, 5, 10, 8]
m = 2
low, high = max(nums), sum(nums)
while low < high:
    mid = (low + high) // 2
    if can_split(nums, m, mid):
        high = mid
    else:
        low = mid + 1
print(low)

What is the output of this code?

medium

A. 15

B. 18

C. 20

D. 10

Solution

1. Step 1: Understand the problem and initial bounds

   We want to split nums into 2 subarrays minimizing the maximum sum. low = max(nums) = 10, high = sum(nums) = 32.

2. Step 2: Trace binary search iterations

   - mid=21: True ([7,2,5]=14, [10,8]=18 <=21), high=21
   - mid=15: False (requires 3 subarrays), low=16
   - mid=18: True, high=18
   - mid=17: False, low=18
   Final low=18.

3. Final Answer:

   18 -> Option B

4. Quick Check:

   Minimum max load for 2 splits = 18 [OK]

Hint: Check mid as max load and validate splits [OK]

Common Mistakes:

• Not setting low as max element
• Confusing count of subarrays
• Off-by-one errors in loop conditions

4. The following code tries to find the minimum maximum time to complete tasks by workers using binary search on answer. Identify the bug:

def can_finish(tasks, workers, max_time):
    count = 1
    current_time = 0
    for t in tasks:
        if t > max_time:
            return False
        if current_time + t <= max_time:
            current_time += t
        else:
            count += 1
            current_time = t
    return count <= workers

tasks = [3, 6, 7, 11]
workers = 2
low, high = 0, sum(tasks)
while low < high:
    mid = (low + high) // 2
    if can_finish(tasks, workers, mid):
        high = mid
    else:
        low = mid + 1
print(low)

medium

A. The current_time should reset to 0 instead of t after incrementing count

B. The function should return count < workers instead of <= workers

C. The loop condition should be while low <= high

D. Initial low should be max(tasks), not 0

Solution

1. Step 1: Check initial binary search bounds

   Low is set to 0, but minimum max_time must be at least max(tasks) because no task can be split.

2. Step 2: Understand effect of wrong low

   Starting low at 0 causes unnecessary checks and may cause infinite loop or wrong answer.

3. Final Answer:

   Initial low should be max(tasks), not 0 -> Option D

4. Quick Check:

   Low bound must be max task time [OK]

Hint: Set low to max task time to avoid invalid guesses [OK]

Common Mistakes:

• Setting low to 0 instead of max(tasks)
• Wrong loop condition causing infinite loops
• Resetting current_time incorrectly

5. You want to find the minimum largest sum when splitting an array nums into k subarrays. However, some elements can be zero or negative. How should you modify the binary search on answer approach to handle this correctly?

hard

A. Set low to min(nums) and high to sum of absolute values of nums, then apply binary search with adjusted checks.

B. Ignore negative values and treat them as zero, then apply normal binary search on answer.

C. Use normal binary search with low as max(nums) and high as sum(nums) without changes.

D. Sort the array first, then apply binary search on answer with low as 0 and high as sum(nums).

Solution

1. Step 1: Identify problem with negative and zero values

   Negative values can reduce sums, so max(nums) may be negative or zero, and sum(nums) may be less than max(nums).

2. Step 2: Adjust binary search bounds

   Set low to minimum element (which can be negative) and high to sum of absolute values to cover all possible sums.

3. Step 3: Modify check function

   Check function must handle negative sums correctly and validate splits accordingly.

4. Final Answer:

   Set low to min(nums) and high to sum of absolute values of nums, then apply binary search with adjusted checks. -> Option A

5. Quick Check:

   Adjust bounds for negatives and zeros [OK]

Hint: Adjust low/high bounds when negatives exist [OK]

Common Mistakes:

• Using max(nums) as low when negatives exist
• Ignoring negative values in sums
• Assuming sums are always positive