Binary Search on Answer Technique in DSA Go - 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 Go code that uses binary search on answer to find the minimum largest sum when splitting an array into 2 subarrays?

DSA Go

package main
import "fmt"
func canSplit(nums []int, maxSum int, m int) bool {
    count, currentSum := 1, 0
    for _, num := range nums {
        if currentSum+num > maxSum {
            count++
            currentSum = num
            if count > m {
                return false
            }
        } else {
            currentSum += num
        }
    }
    return true
}
func splitArray(nums []int, m int) int {
    left, right := 0, 0
    for _, num := range nums {
        if num > left {
            left = num
        }
        right += num
    }
    for left < right {
        mid := (left + right) / 2
        if canSplit(nums, mid, m) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}
func main() {
    nums := []int{7, 2, 5, 10, 8}
    m := 2
    fmt.Println(splitArray(nums, m))
}

A 13

B 15

C 20

D 18

💡 Hint

Think about how binary search narrows down the maximum allowed subarray sum to split into m parts.

The code finds the minimum largest sum among 2 subarrays. The answer is 18 because splitting as [7,2,5] and [10,8] gives sums 14 and 18, and 18 is the smallest maximum sum possible.

🧠 Conceptual

intermediate

Understanding Binary Search on Answer Technique

Which statement best describes the binary search on answer technique?

A It uses binary search on a range of possible answers to find the optimal solution.

B It sorts the array first and then applies binary search to find an element.

C It applies binary search on the input array elements directly to find a target value.

D It uses binary search to find the median of the array.

💡 Hint

Think about searching over possible answers, not array elements.

Binary search on answer searches over a range of possible answers (like sums, lengths) to find the best valid answer, not directly on array elements.

🔧 Debug

advanced

Identify the error in binary search on answer implementation

What error does the following Go code produce when run? It tries to find the minimum maximum subarray sum for splitting into m parts.

DSA Go

package main
import "fmt"
func canSplit(nums []int, maxSum int, m int) bool {
    count, currentSum := 1, 0
    for _, num := range nums {
        if currentSum+num >= maxSum {
            count++
            currentSum = num
            if count > m {
                return false
            }
        } else {
            currentSum += num
        }
    }
    return true
}
func splitArray(nums []int, m int) int {
    left, right := 0, 0
    for _, num := range nums {
        if num > left {
            left = num
        }
        right += num
    }
    for left < right {
        mid := (left + right) / 2
        if canSplit(nums, mid, m) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}
func main() {
    nums := []int{7, 2, 5, 10, 8}
    m := 2
    fmt.Println(splitArray(nums, m))
}

A The code causes a runtime panic due to index out of range.

B The code outputs 18, which is the correct answer.

C The code outputs 19, which is incorrect for the problem.

D The code causes an infinite loop due to incorrect condition in canSplit.

💡 Hint

Check the condition that decides when to split the subarray.

The condition 'currentSum+num >= maxSum' causes splitting too early, leading to a wrong answer 19 instead of 18.

🚀 Application

advanced

Using Binary Search on Answer to Minimize Maximum Distance

You have positions of gas stations on a highway as [1, 2, 8, 12, 17]. You want to add 2 more stations to minimize the maximum distance between adjacent stations. What is the minimized maximum distance after adding 2 stations?

A 5

B 4

C 3

D 6

💡 Hint

Use binary search on the distance and check feasibility by counting required stations.

By binary searching the max distance and checking how many stations are needed, the minimum max distance achievable is 4.

❓ Predict Output

expert

Output of Binary Search on Answer for Painter Partition Problem

What is the output of this Go code that uses binary search on answer to find the minimum time to paint all boards by 3 painters?

DSA Go

package main
import "fmt"
func isPossible(boards []int, maxTime int, painters int) bool {
    total, count := 0, 1
    for _, time := range boards {
        if time > maxTime {
            return false
        }
        if total+time > maxTime {
            count++
            total = time
            if count > painters {
                return false
            }
        } else {
            total += time
        }
    }
    return true
}
func minTime(boards []int, painters int) int {
    left, right := 0, 0
    for _, time := range boards {
        if time > left {
            left = time
        }
        right += time
    }
    for left < right {
        mid := (left + right) / 2
        if isPossible(boards, mid, painters) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}
func main() {
    boards := []int{10, 20, 30, 40}
    painters := 3
    fmt.Println(minTime(boards, painters))
}

A 40

B 50

C 60

D 30

💡 Hint

Think about how painters can split boards to minimize maximum painting time.

The minimum time is 40 by assigning boards as [10,20], [30], [40].

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, then adjust the guess using binary search.

B. We sort the input array before applying binary search.

C. We use binary search to find an element in a sorted array.

D. We use recursion to divide the problem into smaller subproblems.

Solution

1. Step 1: Understand the technique concept

   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 too high or too low, we adjust it using binary search until the best answer is found.

3. Final Answer:

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

4. Quick Check:

   Guess and check with binary search = D [OK]

Hint: Think guess-check-adjust using binary search [OK]

Common Mistakes:

• Confusing with normal binary search on arrays
• Thinking it always requires sorting input
• Assuming recursion is mandatory

2. Which of the following is the correct Go syntax to start a binary search on answer between low = 1 and high = 100?

easy

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

B. for i := low; i < high; i++ { mid := (low + high) / 2 }

C. for low <= high { mid := (low + high) / 2 }

D. if low < high { mid := (low + high) / 2 }

Solution

1. Step 1: Identify Go loop syntax for binary search

   Go uses for loops for iteration; for low <= high { ... } is correct for binary search.

2. Step 2: Check other options for syntax errors

   while is not valid in Go; for i := low; i < high; i++ is a counting loop, not binary search; if is conditional, not loop.

3. Final Answer:

   for low <= high { mid := (low + high) / 2 } -> Option C

4. Quick Check:

   Go binary search loop uses for low <= high [OK]

Hint: Use for loop with condition low <= high in Go [OK]

Common Mistakes:

• Using while loop (not valid in Go)
• Using for with increment instead of condition
• Using if instead of loop

3. Consider the following Go code snippet using binary search on answer to find the minimum x such that x*x >= 10:

low, high := 1, 10
var ans int
for low <= high {
  mid := (low + high) / 2
  if mid*mid >= 10 {
    ans = mid
    high = mid - 1
  } else {
    low = mid + 1
  }
}
fmt.Println(ans)

What will be printed?

medium

A. 3

B. 4

C. 10

D. 1

Solution

1. Step 1: Trace binary search for x where x*x >= 10

   Check mid values: - mid=5: 25 >=10 true, ans=5, high=4 - mid=2: 4 >=10 false, low=3 - mid=3: 9 >=10 false, low=4 - mid=4: 16 >=10 true, ans=4, high=3 Loop ends, ans=4

2. Step 2: Find minimum x satisfying condition

   Minimum x with x*x >=10 is 4, so ans=4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Minimum x with x²≥10 is 4 [OK]

Hint: Check mid² against target, adjust low/high accordingly [OK]

Common Mistakes:

• Choosing mid incorrectly (integer division errors)
• Not updating ans when condition is true
• Confusing >= with >

4. The following Go code tries to find the maximum length of a rope that can be cut into at least k pieces using binary search on answer. Identify the bug:

func maxRopeLength(ropes []int, k int) int {
  low, high := 1, 0
  for _, r := range ropes {
    if r > high {
      high = r
    }
  }
  ans := 0
  for low < high {
    mid := (low + high) / 2
    count := 0
    for _, r := range ropes {
      count += r / mid
    }
    if count >= k {
      ans = mid
      low = mid + 1
    } else {
      high = mid - 1
    }
  }
  return ans
}

medium

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

B. The initial high value should be 1, not 0.

C. The count calculation should use float division, not integer division.

D. The ans variable should be initialized to high, not 0.

Solution

1. Step 1: Analyze binary search loop condition

   The loop uses for low < high, which misses the case when low == high, possibly skipping the final answer.

2. Step 2: Correct loop condition for binary search

   Changing to for low <= high ensures all candidates are checked, including when low equals high.

3. Final Answer:

   The loop condition should be low <= high, not low < high. -> Option A

4. Quick Check:

   Binary search loops use low <= high [OK]

Hint: Use low <= high to include all candidates in binary search [OK]

Common Mistakes:

• Using low < high and missing final check
• Confusing integer and float division here
• Initializing ans incorrectly

5. You want to find the minimum maximum workload to assign n tasks to m workers so that no worker has workload exceeding that value. You have an array of task times. Which approach correctly applies binary search on answer to solve this problem?

hard

A. Use binary search on the number of workers instead of workload.

B. Set low as 0, high as max task time; binary search on this range checking if sum of tasks is less than high.

C. Sort tasks and binary search for the task with median time as answer.

D. Set low as max task time, high as sum of all tasks; binary search on this range checking feasibility of workload limit.

Solution

1. Step 1: Define search space for answer

   The minimum maximum workload must be at least the largest single task time (low) and at most the sum of all tasks (high).

2. Step 2: Check feasibility in binary search

   For each mid in [low, high], check if tasks can be assigned to m workers without exceeding mid workload per worker.

3. Step 3: Adjust search based on feasibility

   If feasible, try smaller max workload (high = mid - 1), else increase (low = mid + 1).

4. Final Answer:

   Set low as max task time, high as sum of all tasks; binary search on this range checking feasibility of workload limit. -> Option D

5. Quick Check:

   Search between max task and sum, check feasibility [OK]

Hint: Search between max single task and total sum [OK]

Common Mistakes:

• Setting low to 0 ignoring max task time
• Searching on wrong variable like number of workers
• Not checking feasibility properly