Given an integer array arr and a target value target, return the integer value such that when we change all the integers larger than value in the given array to be equal to value, the sum of the array gets as close as possible (in absolute difference) to target.

In case of a tie, return the minimum such integer.

Notice that the answer is not neccesarilly a number from arr.

&nbsp;
Example 1:

Input: arr = [4,9,3], target = 10
Output: 3
Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.


Example 2:

Input: arr = [2,3,5], target = 10
Output: 5


Example 3:

Input: arr = [60864,25176,27249,21296,20204], target = 56803
Output: 11361


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 104
	1 &lt;= arr[i], target &lt;= 105


class Solution:
    def findBestValue(self, arr: List[int], t: int) -> int:
        def getsum(x):
            s = 0
            for i in range(n):
                if arr[i] > x:
                    s += x*(n-i)
                    break
                else:
                    s += arr[i]
            return s
			
		arr.sort()
        n = len(arr)
        l, r = 0, max(arr)
        ans = [inf, inf]
        while l <= r:
            m = l+(r-l)//2
            if abs(getsum(m)-t) <= ans[0]:
                if abs(getsum(m)-t) == ans[0]:
                    ans[1] = min(m, ans[1])
                else:
                    ans = [abs(getsum(m)-t), m]
            if getsum(m) > t:
                r = m-1
            else:
                l = m+1
        
        return ans[1]
class Solution {
    int max = 0;
    int len;
    public int findBestValue(int[] arr, int target) {
        this.len = arr.length;

        for (int i = 0; i < len; i++)
            max = Math.max(max, arr[i]);

        int l = 0;
        int r = max;
        while(l < r){
            int mid = l + (r-l) / 2;

            if(check(arr, mid, target) <= check(arr, mid+1, target))
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }

    private int check(int[] arr, int value, int target){
        int sum = 0;
        for(int e : arr){
            if(e > value)
                sum += value;
            else
                sum += e;
        }

        return Math.abs(sum-target);
    }
}
// This Question Includes Both Binary Search And bit of Greedy Concept also.
// See We Know Ans Always Lies Between 0 and maximum element according to given question condition Because
// sum value at maximum element is same as any other element greater than it.
// So we get our sum from getval function after that you need to choose as to move forward(l = mid+1) or backward
// i.e.(h = mid-1) so if sum value we obtain is less than target then l = mid+1 why so??
// Because 2 3 5 lets suppose you are having this array if we pick 2 as mid then sum value will be 6 whereas if we pick 3 then sum value will be 8 and 10 when we pick 5 so notice that sum will increase when we increase value and
// correspondingly decrease when we decrease value...So yess This is all what we did and got Accepted.
class Solution {
public:
    int getval(int mid , vector<int>&arr)
    {
        int sum = 0;
        for(int i = 0 ; i < arr.size() ; i++)
        {
            if(arr[i] > mid)
                sum+=mid;
            else
                sum+=arr[i];
        }
        return sum;
    }
    int findBestValue(vector<int>& arr, int target) {
        int n = arr.size();
        int l = 0 , h = *max_element(arr.begin(),arr.end());
        int ans = 0, min1 = INT_MAX;
        while(l<=h)
        {
            int mid = l + (h-l)/2;
            int k = getval(mid,arr);
            if(k==target)
            {
                return mid;
            }
            else if(k<target)
            {
                l = mid+1;
            }
            else
                h = mid -1;

            int j = abs(k - target);
            if(j<min1)
            {
                min1 = j;
                ans = mid;
            }
            else if(j==min1)
            {
                ans = min(ans , mid);
            }
        }
        return ans;
    }
};
/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var findBestValue = function(arr, target) {
    const sortedArr = [...arr].sort(function (a, b) {  return a - b;  });
    var lowestValue = Math.min(sortedArr[arr.length-1], Math.floor(target/arr.length));
    var higestValue = Math.min(sortedArr[arr.length-1], target);
    var value, deltaLeft, deltaRight;
    
    while (true) {
        candidateRight = Math.ceil((lowestValue + higestValue)/2)
        candidateLeft = candidateRight - 1
        deltaLeft = calculateDeltaForCandidate(sortedArr, target, candidateLeft)
        if (deltaLeft == 0) {
            return candidateLeft
        }
        deltaRight = calculateDeltaForCandidate(sortedArr, target, candidateRight)
        if (deltaRight == 0) {
            return candidateRight
        }
        if (deltaRight == 0) {
            return candidateRight
        }
        if (candidateRight == higestValue) {
            return deltaLeft <= deltaRight ? candidateLeft : candidateRight;
        }
        if (deltaLeft <= deltaRight) {
            higestValue = candidateLeft
        } else {
            lowestValue = candidateRight
        }
    }
};

var calculateDeltaForCandidate = function(sArr, target, candidate) {
    var sum
    //find idx lover then candidate
    for (var i=0; i < sArr.length; i++) {
        if (sArr[i] >= candidate) {
            sum = sArr.slice(0, i).reduce((partialSum, a) => partialSum + a, 0) + (sArr.length - i) * candidate;
            return Math.abs(sum - target)
        };
    }
    return NaN
};
Sum of Mutated Array Closest to Target