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

DSA Rust

fn can_split(nums: &[i32], max_sum: i32, m: i32) -> bool {
    let mut current_sum = 0;
    let mut 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;
        }
    }
    true
}

fn split_array(nums: Vec<i32>, m: i32) -> i32 {
    let mut left = *nums.iter().max().unwrap();
    let mut right: i32 = nums.iter().sum();
    while left < right {
        let mid = left + (right - left) / 2;
        if can_split(&nums, mid, m) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    left
}

fn main() {
    let nums = vec![7, 2, 5, 10, 8];
    let m = 2;
    println!("{}", split_array(nums, m));
}

A 15

B 20

C 18

D 13

💡 Hint

Think about splitting the array into 2 subarrays such that the largest sum is minimized.

The code finds the smallest maximum subarray sum when splitting the array into 2 parts. The correct answer is 18 because splitting as [7,2,5] and [10,8] gives sums 14 and 18, and 18 is the minimal largest sum possible.

🧠 Conceptual

intermediate

Understanding the Role of the Check Function in Binary Search on Answer

In the binary search on answer technique, what is the main purpose of the 'check' function?

A To verify if a guessed answer satisfies the problem constraints

B To sort the input data before binary searching

C To calculate the exact answer directly without searching

D To generate all possible answers for comparison

💡 Hint

Think about how binary search narrows down the answer range.

The 'check' function tests if the current guessed answer is valid under problem constraints, guiding the binary search to move left or right.

🔧 Debug

advanced

Identify the Logical Error in Binary Search on Answer Implementation

What is the logical error in the following Rust code snippet for binary search on answer?

DSA Rust

fn can_place_cows(stalls: &[i32], dist: i32, cows: i32) -> bool {
    let mut count = 1;
    let mut last_position = stalls[0];
    for &stall in stalls.iter().skip(1) {
        if stall - last_position >= dist {
            count += 1;
            last_position = stall;
        }
;    }
    count >= cows
}

fn aggressive_cows(stalls: Vec<i32>, cows: i32) -> i32 {
    let mut stalls = stalls;
    stalls.sort();
    let mut left = 0;
    let mut right = stalls[stalls.len() - 1] - stalls[0];
    while left < right {
        let mid = left + (right - left) / 2;
        if can_place_cows(&stalls, mid, cows) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    left
}

A The initial left value should be 1 instead of 0

B The binary search updates left and right incorrectly, causing off-by-one error

C The can_place_cows function does not count cows correctly

D The stalls array is not sorted before use

💡 Hint

Check how left and right pointers are updated in binary search.

The binary search moves left to mid + 1 when can_place_cows returns true, which skips the correct answer. It should move right to mid to find the maximum minimum distance.

❓ Predict Output

advanced

Output of Binary Search on Answer for Painter Partition Problem

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

DSA Rust

fn is_possible(boards: &[i32], k: i32, mid: i32) -> bool {
    let mut painters = 1;
    let mut time = 0;
    for &board in boards {
        if board > mid {
            return false;
        }
        if time + board > mid {
            painters += 1;
            time = board;
            if painters > k {
                return false;
            }
        } else {
            time += board;
        }
    }
    true
}

fn min_time(boards: Vec<i32>, k: i32) -> i32 {
    let mut left = *boards.iter().max().unwrap();
    let mut right: i32 = boards.iter().sum();
    while left < right {
        let mid = left + (right - left) / 2;
        if is_possible(&boards, k, mid) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    left
}

fn main() {
    let boards = vec![10, 20, 30, 40];
    let k = 2;
    println!("{}", min_time(boards, k));
}

A 50

B 40

C 70

D 60

💡 Hint

Try splitting boards between 2 painters to minimize the maximum painting time.

Splitting as [10,20,30] and [40] gives max time 60, but [10,20] and [30,40] gives max time 70. The minimal max time is 50 by splitting as [10,20] and [30,40].

🧠 Conceptual

expert

Why is Binary Search on Answer Suitable for Optimization Problems?

Why is the binary search on answer technique particularly suitable for optimization problems with monotonic constraints?

A Because it converts the problem into a graph traversal

B Because it enumerates all possible answers to find the best one

C Because it uses recursion to explore all subproblems

D Because the solution space is sorted and the feasibility check is monotonic, allowing efficient narrowing

💡 Hint

Think about how binary search exploits order in the solution space.

Binary search on answer works when the feasibility of a guessed answer changes monotonically, enabling efficient search without checking all possibilities.

Practice

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

easy

A. We guess an answer and use binary search to find the smallest or largest valid value.

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

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

D. We apply binary search to find the maximum element in an unsorted array.

Solution

1. Step 1: Understand the technique purpose

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

2. Step 2: Use binary search to narrow answer range

   By checking mid-values and adjusting search space, we find the smallest or largest valid answer efficiently.

3. Final Answer:

   We guess an answer and use binary search to find the smallest or largest valid value. -> Option A

4. Quick Check:

   Binary Search on Answer = Guess + Check + Narrow [OK]

Hint: Think of guessing answers and checking validity with binary search [OK]

Common Mistakes:

• Confusing it with normal binary search on sorted arrays
• Thinking it finds elements, not answers
• Assuming it works only on arrays

2. Which of the following Rust code snippets correctly initializes the binary search boundaries for searching an answer between 1 and 100?

easy

A. let mut low = 0; let mut high = 101;

B. let mut low = 0; let mut high = 100;

C. let mut low = 1; let mut high = 101;

D. let mut low = 1; let mut high = 100;

Solution

1. Step 1: Identify correct search range

   The problem states searching between 1 and 100 inclusive, so low should be 1 and high 100.

2. Step 2: Check boundary initialization

   let mut low = 1; let mut high = 100; sets low = 1 and high = 100, which matches the problem range exactly.

3. Final Answer:

   let mut low = 1; let mut high = 100; -> Option D

4. Quick Check:

   Boundaries match problem range [OK]

Hint: Set low and high exactly to the problem's answer range [OK]

Common Mistakes:

• Starting low at 0 when range starts at 1
• Setting high to 101 which is outside the range
• Confusing inclusive and exclusive boundaries

3. Consider this Rust function using binary search on answer to find the minimum x such that x*x >= 10:

fn binary_search_answer() -> i32 {
    let mut low = 1;
    let mut high = 10;
    while low < high {
        let mid = (low + high) / 2;
        if mid * mid >= 10 {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    low
}

fn main() {
    println!("{}", binary_search_answer());
}

What is the output when this program runs?

medium

A. 4

B. 5

C. 10

D. 3

Solution

1. Step 1: Understand the search condition

   We want the smallest x where x*x >= 10. Squares: 3*3=9 (no), 4*4=16 (yes).

2. Step 2: Trace binary search steps

   Initial low=1, high=10 mid=5, 5*5=25 >=10, high=5 mid=3, 3*3=9 <10, low=4 mid=4, 4*4=16 >=10, high=4 Now low=4, high=4, loop ends, returns low=4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Minimum x with x*x >= 10 is 4 [OK]

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

Common Mistakes:

• Returning mid instead of low after loop
• Off-by-one errors in updating low or high
• Confusing condition direction (>= vs >)

4. The following Rust code tries to find the maximum x such that x*x <= 20 using binary search on answer. What is the bug?

fn max_x() -> i32 {
    let mut low = 0;
    let mut high = 20;
    while low <= high {
        let mid = (low + high) / 2;
        if mid * mid <= 20 {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    high
}

medium

A. The loop condition should be 'low < high' instead of 'low <= high'.

B. The update 'low = mid' can cause infinite loop when low == mid.

C. The function should return 'low' instead of 'high'.

D. The initial 'high' should be 21, not 20.

Solution

1. Step 1: Analyze loop update statements

   When mid equals low, setting low = mid does not change low, causing infinite loop.

2. Step 2: Identify fix for infinite loop

   To avoid infinite loop, update low to mid + 1 when condition holds.

3. Final Answer:

   The update 'low = mid' can cause infinite loop when low == mid. -> Option B

4. Quick Check:

   Update low to mid + 1 to progress loop [OK]

Hint: Always move low or high past mid to avoid infinite loops [OK]

Common Mistakes:

• Not updating low or high correctly causing infinite loops
• Returning wrong boundary after loop ends
• Confusing loop condition operators

5. You want to find the minimum time required to complete all tasks given an array of task durations and a maximum allowed time. Using binary search on answer, which approach correctly finds the minimum maximum time per worker if tasks must be assigned in order and each worker can do consecutive tasks only? Choose the correct high-level approach.

hard

A. Use binary search to find the worker count, then assign tasks randomly.

B. Sort tasks and binary search for the task with maximum duration to assign first.

C. Binary search the answer range of time, and for each mid, greedily assign tasks to workers checking if all tasks fit within mid time.

D. Apply binary search on the number of tasks, splitting tasks evenly among workers.

Solution

1. Step 1: Define answer range and check function

   We binary search over possible maximum time per worker. For each mid, we check if tasks can be assigned in order without exceeding mid time per worker.

2. Step 2: Greedy assignment check

   Assign tasks to workers greedily, moving to next worker when current sum exceeds mid. If all tasks fit within allowed workers, mid is valid.

3. Final Answer:

   Binary search the answer range of time, and for each mid, greedily assign tasks to workers checking if all tasks fit within mid time. -> Option C

4. Quick Check:

   Binary Search on Answer + Greedy check = Correct approach [OK]

Hint: Binary search answer, check feasibility with greedy assignment [OK]

Common Mistakes:

• Sorting tasks when order matters
• Binary searching worker count instead of time
• Assigning tasks randomly ignoring order