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 of subarrays?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

bool canSplit(const vector<int>& nums, int m, int maxSum) {
    int currentSum = 0, count = 1;
    for (int num : nums) {
        if (num > maxSum) return false;
        if (currentSum + num > maxSum) {
            count++;
            currentSum = num;
            if (count > m) return false;
        } else {
            currentSum += num;
        }
    }
    return true;
}

int splitArray(vector<int>& nums, int m) {
    int left = 0, right = 0;
    for (int num : nums) right += num;
    int result = right;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canSplit(nums, m, mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return result;
}

int main() {
    vector<int> nums = {7, 2, 5, 10, 8};
    int m = 2;
    cout << splitArray(nums, m) << endl;
    return 0;
}

A 18

B 15

C 20

D 25

💡 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 with minimum largest sum is {7,2,5} and {10,8}. The sums are 14 and 18, so the answer is 18.

🧠 Conceptual

intermediate

Understanding Binary Search on Answer Technique

Which statement best describes the binary search on answer technique?

A It uses binary search on the input array elements directly to find a target value.

B It applies binary search on a range of possible answers to find the optimal solution.

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

D It uses binary search to split the array into equal halves repeatedly.

💡 Hint

Think about searching over a range of values, not array indices.

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

❓ Predict Output

advanced

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

What is the output of this C++ code that uses binary search on answer to find the minimum time to finish jobs with given workers?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

bool canFinish(const vector<int>& jobs, int workers, int maxTime) {
    int count = 1, currentTime = 0;
    for (int job : jobs) {
        if (job > maxTime) return false;
        if (currentTime + job > maxTime) {
            count++;
            currentTime = job;
            if (count > workers) return false;
        } else {
            currentTime += job;
        }
    }
    return true;
}

int minTime(vector<int>& jobs, int workers) {
    int left = 0, right = 0;
    for (int job : jobs) right += job;
    int result = right;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canFinish(jobs, workers, mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return result;
}

int main() {
    vector<int> jobs = {3, 2, 3};
    int workers = 3;
    cout << minTime(jobs, workers) << endl;
    return 0;
}

A 3

B 4

C 5

D 6

💡 Hint

Each worker can do one job, so minimum time is the longest single job.

With 3 workers and jobs {3,2,3}, each worker can do one job. The longest job is 3, so minimum time is 3.

🔧 Debug

advanced

Identify the error in binary search on answer implementation

What error does the following code produce when run?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

bool canSplit(const vector<int>& nums, int m, int maxSum) {
    int currentSum = 0, count = 1;
    for (int num : nums) {
        if (num > maxSum) return false;
        if (currentSum + num >= maxSum) {
            count++;
            currentSum = num;
            if (count > m) return false;
        } else {
            currentSum += num;
        }
    }
    return true;
}

int splitArray(vector<int>& nums, int m) {
    int left = 0, right = 0;
    for (int num : nums) right += num;
    int result = right;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canSplit(nums, m, mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return result;
}

int main() {
    vector<int> nums = {7, 2, 5, 10, 8};
    int m = 2;
    cout << splitArray(nums, m) << endl;
    return 0;
}

A Infinite loop

B Outputs 18

C Outputs 17

D Outputs 20

💡 Hint

Check the condition that decides when to split the subarray.

The condition uses '>=' instead of '>' causing splits earlier than needed, resulting in a wrong answer 17 instead of 18.

🚀 Application

expert

Minimum Largest Distance to Gas Station

Given an array of gas station positions and an integer k representing additional gas stations to add, what is the minimum possible maximum distance between adjacent gas stations after adding k stations? Consider the code below. What is the output?

DSA C++

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

bool canPlace(const vector<int>& stations, int k, double maxDist) {
    int count = 0;
    for (int i = 1; i < stations.size(); i++) {
        double dist = stations[i] - stations[i - 1];
        count += (int)(dist / maxDist);
        if (count > k) return false;
    }
    return true;
}

double minmaxGasDist(vector<int>& stations, int k) {
    double left = 0, right = stations.back() - stations.front();
    for (int i = 0; i < 100; i++) {
        double mid = (left + right) / 2;
        if (canPlace(stations, k, mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return right;
}

int main() {
    vector<int> stations = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int k = 9;
    cout.precision(6);
    cout << fixed << minmaxGasDist(stations, k) << endl;
    return 0;
}

A 1.000000

B 0.750000

C 0.900000

D 0.500000

💡 Hint

Adding 9 stations between 10 stations can reduce max distance to 0.5.

The code binary searches the max distance and finds 0.5 as the minimum max distance after adding 9 stations.

Practice

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

easy

A. Searching for the answer by repeatedly dividing the search space based on feasibility

B. Sorting the array before applying binary search

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

D. Applying binary search only on arrays with unique elements

Solution

1. Step 1: Understand the problem context

   Binary Search on Answer is used when the answer lies within a range and we can check feasibility for a candidate answer.

2. Step 2: Apply binary search on the answer range

   We repeatedly pick a middle value and check if it satisfies the problem's conditions, narrowing the search space accordingly.

3. Final Answer:

   Searching for the answer by repeatedly dividing the search space based on feasibility -> Option A

4. Quick Check:

   Binary Search on Answer = feasibility check [OK]

Hint: Think of binary search on answer as guessing and checking [OK]

Common Mistakes:

• Confusing it with normal binary search on arrays
• Not checking feasibility properly
• Trying to apply it on unsorted data without a valid range

2. Which of the following is the correct syntax to start a binary search on answer for an integer range low to high in C++?

easy

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

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

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

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

Solution

1. Step 1: Identify the correct loop condition

   Binary search typically uses a loop with condition low < high to avoid infinite loops and handle edge cases.

2. Step 2: Calculate mid safely

   Using mid = low + (high - low) / 2 prevents integer overflow compared to (low + high) / 2.

3. Final Answer:

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

4. Quick Check:

   Safe mid calculation with proper loop [OK]

Hint: Use low + (high - low)/2 to avoid overflow [OK]

Common Mistakes:

• Using <= in loop causing infinite loops
• Calculating mid as (low + high)/2 risking overflow
• Using for loop instead of while for binary search

3. Consider the following code snippet that uses binary search on answer to find the minimum maximum load for dividing an array into k subarrays:

bool canDivide(const vector<int>& arr, int k, int maxLoad) {
    int currentSum = 0, count = 1;
    for (int num : arr) {
        if (num > maxLoad) return false;
        if (currentSum + num > maxLoad) {
            count++;
            currentSum = num;
        } else {
            currentSum += num;
        }
    }
    return count <= k;
}

int binarySearchAnswer(const vector<int>& arr, int k) {
    int low = 0, high = 0;
    for (int num : arr) high += num;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (canDivide(arr, k, mid)) high = mid;
        else low = mid + 1;
    }
    return low;
}

int main() {
    vector<int> arr = {7, 2, 5, 10, 8};
    int k = 2;
    cout << binarySearchAnswer(arr, k) << endl;
}

What is the output of this program?

medium

A. 15

B. 18

C. 20

D. 22

Solution

1. Step 1: Understand the problem and code

   The code finds the minimum maximum sum when dividing the array into 2 subarrays. The total sum is 7+2+5+10+8=32.

2. Step 2: Trace binary search on answer

   Check mid values and feasibility:
   - mid=16: canDivide returns true (possible, e.g., subarrays sums 14 and 18)
   - mid=15: canDivide returns true (possible, e.g., subarrays sums 14 and 15)
   - mid=14: canDivide returns false (cannot split into 2 with max sum 14)
   Binary search narrows down to 15 as minimum max load.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Minimum max load = 15 [OK]

Hint: Sum array, binary search between 0 and sum [OK]

Common Mistakes:

• Not checking if single element > mid
• Incorrectly updating low and high
• Misunderstanding feasibility function

4. The following code attempts to find the smallest maximum weight capacity to ship packages within D days using binary search on answer. Identify the bug:

bool canShip(const vector<int>& weights, int D, int capacity) {
    int days = 1, currentLoad = 0;
    for (int w : weights) {
        if (w > capacity) return false;
        if (currentLoad + w > capacity) {
            days++;
            currentLoad = w;
        } else {
            currentLoad += w;
        }
    }
    return days <= D;
}

int shipWithinDays(const vector<int>& weights, int D) {
    int low = 0, high = accumulate(weights.begin(), weights.end(), 0);
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canShip(weights, D, mid)) high = mid - 1;
        else low = mid + 1;
    }
    return low;
}

medium

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

B. The mid calculation can cause integer overflow

C. The canShip function does not handle empty weights array

D. The initial value of low should be the maximum weight in the array, not 0

Solution

1. Step 1: Analyze initial search range

   Low should start at the maximum single package weight because capacity cannot be less than the heaviest package.

2. Step 2: Identify impact of wrong low value

   Starting low at 0 causes unnecessary checks and may cause incorrect results or longer runtime.

3. Final Answer:

   The initial value of low should be the maximum weight in the array, not 0 -> Option D

4. Quick Check:

   Low = max(weights) [OK]

Hint: Low must be max element, high sum of all [OK]

Common Mistakes:

• Starting low at 0 instead of max element
• Using <= in loop causing off-by-one errors
• Ignoring edge cases with large weights

5. You want to find the minimum time required to complete n tasks using m machines, where each machine can complete one task in a fixed time given by array times. You can assign multiple tasks to a machine but tasks are done sequentially. Using binary search on answer, which approach correctly finds the minimum time to finish all tasks?

Choose the correct approach:

hard

A. Binary search on number of machines from 1 to m, checking if tasks can be done in fixed time

B. Binary search on time range from 0 to max(times) * n, and check if total tasks done by all machines in mid time is at least n

C. Sort times and pick the machine with minimum time multiplied by n

D. Use binary search on tasks from 1 to n, checking if tasks fit in given time

Solution

1. Step 1: Define search space for binary search

   The minimum time is 0 and maximum time is max machine time * n tasks (worst case all tasks on slowest machine).

2. Step 2: Check feasibility at mid time

   Calculate total tasks all machines can complete in mid time by summing floor(mid / times[i]). If total tasks >= n, mid time is feasible.

3. Step 3: Narrow search space

   If feasible, try smaller time by setting high = mid; else low = mid + 1.

4. Final Answer:

   Binary search on time range from 0 to max(times) * n, and check if total tasks done by all machines in mid time is at least n -> Option B

5. Quick Check:

   Binary search on time with feasibility check [OK]

Hint: Search time range, count tasks done at mid [OK]

Common Mistakes:

• Binary searching on machines instead of time
• Not summing tasks correctly for feasibility
• Ignoring sequential task processing per machine