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

DSA C#

using System;

class Program {
    static bool CanSplit(int[] nums, int m, int maxSum) {
        int currentSum = 0, count = 1;
        foreach (var num in nums) {
            if (currentSum + num > maxSum) {
                count++;
                currentSum = num;
                if (count > m) return false;
            } else {
                currentSum += num;
            }
        }
        return true;
    }

    static int SplitArray(int[] nums, int m) {
        int left = 0, right = 0;
        foreach (var num in 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;
    }

    static void Main() {
        int[] nums = {7, 2, 5, 10, 8};
        int m = 2;
        Console.WriteLine(SplitArray(nums, m));
    }
}

A 25

B 15

C 18

D 20

💡 Hint

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

The array [7,2,5,10,8] split into 2 subarrays to minimize the largest sum results in [7,2,5] and [10,8] with sums 14 and 18. The minimum largest sum is 18.

🧠 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 the current guess satisfies the problem constraints

B To sort the input data before binary searching

C To calculate the midpoint between low and high values

D To store intermediate results for memoization

💡 Hint

Think about how binary search narrows down the answer range.

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

🔧 Debug

advanced

Identify the Output or Error of Binary Search on Answer Code

What will be the output or error of this C# code snippet using binary search on answer to find minimum time to complete tasks?

DSA C#

using System;

class Program {
    static bool CanFinish(int[] tasks, int h, int speed) {
        int time = 0;
        foreach (var task in tasks) {
            time += (task + speed - 1) / speed;
        }
        return time <= h;
    }

    static int MinSpeed(int[] tasks, int h) {
        int left = 1, right = 1000000000;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (CanFinish(tasks, h, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    static void Main() {
        int[] tasks = {30, 11, 23, 4, 20};
        int h = 5;
        Console.WriteLine(MinSpeed(tasks, h));
    }
}

A 30

B 23

C Error: Integer overflow

D 20

💡 Hint

Check how the time is calculated and the binary search range.

The minimum speed to finish all tasks in 5 hours is 30, as speed less than 30 requires more than 5 hours.

❓ Predict Output

advanced

Output of Binary Search on Answer for Aggressive Cows Problem

What is the output of this C# code that uses binary search on answer to place cows in stalls maximizing minimum distance?

DSA C#

using System;

class Program {
    static bool CanPlace(int[] stalls, int cows, int dist) {
        int count = 1, lastPos = stalls[0];
        for (int i = 1; i < stalls.Length; i++) {
            if (stalls[i] - lastPos >= dist) {
                count++;
                lastPos = stalls[i];
                if (count == cows) return true;
            }
        }
        return false;
    }

    static int MaxMinDistance(int[] stalls, int cows) {
        Array.Sort(stalls);
        int left = 0, right = stalls[stalls.Length - 1] - stalls[0];
        int result = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (CanPlace(stalls, cows, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

    static void Main() {
        int[] stalls = {1, 2, 8, 4, 9};
        int cows = 3;
        Console.WriteLine(MaxMinDistance(stalls, cows));
    }
}

A 5

B 3

C 4

D 6

💡 Hint

Try placing cows with minimum distance 3 and check feasibility.

The largest minimum distance to place 3 cows in stalls is 3, placing them at positions 1, 4, and 8 (distances 3 and 4) or 1, 4, 9.

🧠 Conceptual

expert

Why is Binary Search on Answer Efficient for Optimization Problems?

Why does the binary search on answer technique provide an efficient solution for certain optimization problems?

A Because it sorts the input data first to speed up calculations

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

C Because it uses dynamic programming to store intermediate results

D Because it reduces the search space logarithmically by checking feasibility of guesses

💡 Hint

Think about how binary search narrows down the range of possible answers.

Binary search on answer narrows the range of possible answers by checking if a guess is valid, reducing complexity from linear to logarithmic in the answer space.

Practice

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

easy

A. We sort the input array and then perform a binary search on the sorted array.

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

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

D. We apply binary search to find the first occurrence of a target value in a list.

Solution

1. Step 1: Understand the technique

   Binary Search on Answer guesses a possible solution and verifies if it meets the problem's conditions. If valid, adjust the guess (smaller/larger) using binary search to find the optimal answer.

2. Final Answer:

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

3. Quick Check:

   Guess and verify with binary search = B [OK]

Hint: Guess answer, check condition, adjust guess with binary search [OK]

Common Mistakes:

• Confusing binary search on answer with normal binary search on array
• Thinking it only works on sorted arrays
• Not verifying the guessed answer properly

2. Which of the following is the correct C# syntax to start a binary search on answer between low and high?

easy

A. do { int mid = (low - high) / 2; } while (low < high);

B. for (int mid = low; mid <= high; mid++) { }

C. if (low < high) { int mid = low + high; }

D. while (low <= high) { int mid = (low + high) / 2; }

Solution

1. Step 1: Identify correct loop and mid calculation

   The binary search loop uses while (low <= high) and mid = (low + high) / 2 with integer division.

2. Final Answer:

   while (low <= high) { int mid = (low + high) / 2; } -> Option D

3. Quick Check:

   Correct binary search loop syntax = A [OK]

Hint: Use while(low <= high) and mid = (low + high) / 2 [OK]

Common Mistakes:

• Using for loop instead of while
• Incorrect mid calculation like (low - high)/2
• Using if instead of loop

3. Consider the following C# code snippet using binary search on answer to find minimum maximum load:

int low = 10, high = 50;
while (low <= high) {
  int mid = (low + high) / 2;
  if (IsPossible(mid))
    high = mid - 1;
  else
    low = mid + 1;
}
Console.WriteLine(low);

If IsPossible(30) returns true and IsPossible(20) returns false, what will be printed?

medium

A. 10

B. 30

C. 21

D. 20

Solution

1. Step 1: Trace binary search behavior

   IsPossible(mid) true means valid (try smaller, high=mid-1); false means invalid (low=mid+1). Given IsPossible(30)=true, IsPossible(20)=false, assuming monotonicity the search converges to smallest valid at 21.

2. Final Answer:

   21 -> Option C

3. Quick Check:

   Minimum valid answer after binary search = 21 [OK]

Hint: Answer is lowest valid mid after binary search ends [OK]

Common Mistakes:

• Printing high instead of low after loop
• Confusing true/false meaning of IsPossible
• Not updating low and high correctly

4. The following code tries to find the minimum maximum load using binary search on answer. What is the bug?

int low = 0, high = maxLoad;
while (low < high) {
  int mid = (low + high) / 2;
  if (IsPossible(mid))
    low = mid;
  else
    high = mid - 1;
}
Console.WriteLine(low);

medium

A. When IsPossible(mid) is true, 'low' should be set to 'mid + 1' instead of 'mid'.

B. When IsPossible(mid) is true, 'high' should be set to 'mid - 1' instead of 'low'.

C. The condition should be 'while (low <= high)' instead of 'while (low < high)'.

D. The mid calculation should be 'mid = low + (high - low) / 2' to avoid overflow.

Solution

1. Step 1: Identify incorrect update causing infinite loop

   When IsPossible(mid) true, low = mid risks no progress (infinite loop if low == mid); should set low = mid + 1 to advance.

2. Final Answer:

   When IsPossible(mid) is true, 'low' should be set to 'mid + 1' instead of 'mid'. -> Option A

3. Quick Check:

   Increment low by 1 to avoid infinite loop [OK]

Hint: Increment low by 1 when condition true to avoid infinite loop [OK]

Common Mistakes:

• Not incrementing low causing infinite loop
• Confusing when to move low or high
• Ignoring loop condition correctness

5. You want to split an array of weights into k contiguous subarrays so that the maximum sum among these subarrays is minimized. Which approach correctly uses binary search on answer to solve this?

hard

A. Binary search between max weight and sum of all weights; check if array can be split into ≤ k parts with max sum ≤ mid.

B. Sort the array and binary search for the kth largest weight.

C. Use binary search on the array indices to find the split points directly.

D. Apply binary search on the number of subarrays from 1 to k.

Solution

1. Step 1: Define search space and feasibility check

   Binary search from max weight (min possible max sum) to total sum; for mid, check if can split into ≤ k contiguous subarrays each with sum ≤ mid. If yes, try smaller mid; else larger.

2. Final Answer:

   Binary search between max weight and sum of all weights; check if array can be split into ≤ k parts with max sum ≤ mid. -> Option A

3. Quick Check:

   Search answer range and verify splits ≤ k [OK]

Hint: Search between max element and total sum, check splits ≤ k [OK]

Common Mistakes:

• Binary searching on indices instead of answer range
• Not checking contiguous subarray sums properly
• Sorting array unnecessarily