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.