Problem

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.

Examples

Example 1

1
2
3

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

1
2

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

Example 3

1
2

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

Constraints

  • 1 <= arr.length <= 10^4
  • 1 <= arr[i], target <= 10^5

Solution

Approach

Sort the array. Use binary search to find the value v such that replacing all elements > v with v makes the sum closest to target. For each candidate v, compute the mutated sum and track the minimum difference.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        sort(arr.begin(), arr.end());
        int n = arr.size();
        vector<int> prefix(n+1);
        for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + arr[i];
        int l = 0, r = arr[n-1], res = 0, diff = INT_MAX;
        while (l <= r) {
            int m = l + (r-l)/2;
            int idx = lower_bound(arr.begin(), arr.end(), m) - arr.begin();
            int s = prefix[idx] + (n-idx)*m;
            if (abs(s - target) < diff || (abs(s - target) == diff && m < res)) {
                res = m; diff = abs(s - target);
            }
            if (s < target) l = m+1;
            else r = m-1;
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class Solution {
    public int findBestValue(int[] arr, int target) {
        Arrays.sort(arr);
        int n = arr.length;
        int[] prefix = new int[n+1];
        for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + arr[i];
        int l = 0, r = arr[n-1], res = 0, diff = Integer.MAX_VALUE;
        while (l <= r) {
            int m = l + (r-l)/2;
            int idx = Arrays.binarySearch(arr, m);
            if (idx < 0) idx = -idx-1;
            int s = prefix[idx] + (n-idx)*m;
            if (Math.abs(s - target) < diff || (Math.abs(s - target) == diff && m < res)) {
                res = m; diff = Math.abs(s - target);
            }
            if (s < target) l = m+1;
            else r = m-1;
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun findBestValue(arr: IntArray, target: Int): Int {
        arr.sort()
        val n = arr.size
        val prefix = IntArray(n+1)
        for (i in 0 until n) prefix[i+1] = prefix[i] + arr[i]
        var l = 0; var r = arr[n-1]; var res = 0; var diff = Int.MAX_VALUE
        while (l <= r) {
            val m = l + (r-l)/2
            val idx = arr.binarySearch(m).let { if (it < 0) -it-1 else it }
            val s = prefix[idx] + (n-idx)*m
            if (kotlin.math.abs(s - target) < diff || (kotlin.math.abs(s - target) == diff && m < res)) {
                res = m; diff = kotlin.math.abs(s - target)
            }
            if (s < target) l = m+1 else r = m-1
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from bisect import bisect_left
class Solution:
    def findBestValue(self, arr: list[int], target: int) -> int:
        arr.sort()
        n = len(arr)
        prefix = [0]*(n+1)
        for i in range(n):
            prefix[i+1] = prefix[i] + arr[i]
        l, r = 0, arr[-1]
        res, diff = 0, float('inf')
        while l <= r:
            m = (l + r) // 2
            idx = bisect_left(arr, m)
            s = prefix[idx] + (n-idx)*m
            if abs(s - target) < diff or (abs(s - target) == diff and m < res):
                res, diff = m, abs(s - target)
            if s < target:
                l = m + 1
            else:
                r = m - 1
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn find_best_value(mut arr: Vec<i32>, target: i32) -> i32 {
        arr.sort();
        let n = arr.len();
        let mut prefix = vec![0; n+1];
        for i in 0..n { prefix[i+1] = prefix[i] + arr[i]; }
        let (mut l, mut r) = (0, arr[n-1]);
        let (mut res, mut diff) = (0, i32::MAX);
        while l <= r {
            let m = l + (r-l)/2;
            let idx = arr.binary_search(&m).unwrap_or_else(|x| x);
            let s = prefix[idx] + (n-idx) as i32 * m;
            if (s - target).abs() < diff || ((s - target).abs() == diff && m < res) {
                res = m; diff = (s - target).abs();
            }
            if s < target { l = m+1; } else { r = m-1; }
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

function findBestValue(arr: number[], target: number): number {
    arr.sort((a, b) => a - b);
    const n = arr.length;
    const prefix = new Array(n+1).fill(0);
    for (let i = 0; i < n; ++i) prefix[i+1] = prefix[i] + arr[i];
    let l = 0, r = arr[n-1], res = 0, diff = Infinity;
    while (l <= r) {
        const m = Math.floor((l + r) / 2);
        let idx = arr.findIndex(x => x >= m);
        if (idx === -1) idx = n;
        const s = prefix[idx] + (n-idx)*m;
        if (Math.abs(s - target) < diff || (Math.abs(s - target) === diff && m < res)) {
            res = m; diff = Math.abs(s - target);
        }
        if (s < target) l = m+1;
        else r = m-1;
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)