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].