Maximum X with subtracted sum at least K using binary search

Given an integer array a[] of size N and a target sum K, subtract a number from each element such that each element becomes X ( if an element is less than X then 0 is subtracted from that element) and the sum of these subtracted numbers is at least K. Choose the numbers in such a way that the value of X is maximum and return X.

Input : N=6, K=8, a[] = {12,15,4,9,12,11}
Output : 10
Explanation : let X = 10, to make a[0] 10, subtract 2 similarly from a[1] subtract 5, for a[2] and a[3] subtract 0 (as both are less than X), then from a[4] subtract 2 and from a[5] subtract 1, so the sum of subtracted numbers are 2+5+0+0+2+1=10 which is greater than K
let X =11,to make a[0] 11 we subtract 1 similarly from a[1] subtract 4, for a[2] and a[3] subtract 0 (as both are less than X), then from a[4] subtract 1 and from a[5] subtract 0, so the sum of subtracted numbers are 1+4+0+0+1+0=6 which is less than K.
Therefore the maximum value of X to make sum of subtracted numbers is 10.
Input : N=5, K=15, a[] ={16,4,9,13,11}
Output : 8
Explanation : sum of subtracted numbers = 8+0+1+5+3=17

Naive Approach :

Consider all the possible values of X that is from 0 to a maximum element of the array, then for each value of X calculate the number of sum of subtracted numbers and return the maximum value of X which satisfies the requirement of at least  K sum.

Optimized Approach :

The idea is to use Binary Search in the search space [ 0, maximum element in a[] ], that is all the possible values of X. In each step, we calculate the mid-value(which is X) and find the sum of subtracted numbers to make the array elements equal to mid(or X). Let that sum=X_sum. Now if X_sum>=K, we search for a larger value that can meet our requirement else we search for a smaller value.

Implementation :

// C++ program to Maximize the array elemnets
// By subtracting, such that the sum
// Of substracted numbers is at least K.
#include <bits/stdc++.h>
using namespace std;

// function to count the coins taken
int cal_XSum(vector<int>& a, int X)
{
    int n = a.size();
    int X_sum = 0;
    for (int i = 0; i < n; i++) {
        // if a[i]>X to make a[i]=X
        // subtact a[i]-X from a[i]
        if (a[i] > X)
            X_sum += (a[i] - X);
    }
    return X_sum;
}

int findMaxX(vector<int>& a, int K)
{
    int n = a.size();
    int left = 0, right = a[0], ans = 0;

    // Lower boundary of the search space is 0
    // Upper boundary is the maximum
    // Element of the array
    for (int i = 1; i < n; i++)
        right = max(right, a[i]);

    // perform Binary Search
    // Over the search space
    while (left <= right) {
        int X = (left + right) / 2;
        int X_Sum = cal_XSum(
            a, X); // sum of the substracted numbers

        // if sum taken is more than K
        // try to find with a higher value of mid
        if (X_Sum >= K) {
            ans = X;
            left = X + 1;
        }

        // Else we need sum to be grater
        // So decrese mid or X  such that
        // Subtracted numbers increase
        else
            right = X - 1;
    }

    return ans;
}

// Driver Code
int main()
{
    vector<int> a = { 12, 15, 4, 9, 12, 11 };
    int K = 8;
    cout << findMaxX(a, K);

    return 0;
}

Output :

10

Time Complexity : O(NlogA), where N is the size of the array and A is the maximum element of the array, for integer values A can have a maximum value of 2^32, so the time complexity can be written as O(32*N).
Auxiliary Space : O(1)