##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1300.html

# 1300. Sum of Mutated Array Closest to Target (Medium)

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.

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


Constraints:

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

Related Topics:
Array, Binary Search

// OJ: https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int findBestValue(vector<int>& A, int target) {
sort(begin(A), end(A));
vector<int> sum = A;
partial_sum(begin(sum), end(sum), begin(sum));
int N = A.size(), L = 0, R = A.back(), minDiff = INT_MAX, ans = R;
while (L <= R) {
int M = (L + R) / 2;
int i = lower_bound(begin(A), end(A), M) - begin(A);
int total = (i - 1 >= 0 ? sum[i - 1] : 0) + (N - i) * M;
int diff = abs(total - target);
if (diff <= minDiff) {
if (diff < minDiff) ans = M;
else ans = min(ans, M);
minDiff = diff;
}
if (total >= target) R = M - 1;
else L = M + 1;
}
return ans;
}
};


## Solution 2.

// OJ: https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/
// Time: O(NlogN)
// Space: O(1)
// Ref: https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/discuss/463306/JavaC%2B%2BPython-Just-Sort-O(nlogn)
class Solution {
public:
int findBestValue(vector<int>& A, int target) {
sort(begin(A), end(A));
int N = A.size(), i = 0;
while (i < N && target > A[i] * (N - i)) target -= A[i++];
return i == N ? A[N - 1] : round((target - 0.0001) / (N - i));
}
};


## Solution 3.

• class Solution {
public int findBestValue(int[] arr, int target) {
Arrays.sort(arr);
int length = arr.length;
int avg = target / length;
if (target % length * 2 > length)
avg++;
if (avg <= arr)
return avg;
int remainSum = target;
int index = 0;
while (avg > arr[index]) {
remainSum -= arr[index];
index++;
int curLength = length - index;
avg = remainSum / curLength;
if (remainSum % curLength * 2 > curLength)
avg++;
}
return avg;
}
}

############

class Solution {
public int findBestValue(int[] arr, int target) {
Arrays.sort(arr);
int n = arr.length;
int[] s = new int[n + 1];
int mx = 0;
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + arr[i];
mx = Math.max(mx, arr[i]);
}
int ans = 0, diff = 1 << 30;
for (int value = 0; value <= mx; ++value) {
int i = search(arr, value);
int d = Math.abs(s[i] + (n - i) * value - target);
if (diff > d) {
diff = d;
ans = value;
}
}
return ans;
}

private int search(int[] arr, int x) {
int left = 0, right = arr.length;
while (left < right) {
int mid = (left + right) >> 1;
if (arr[mid] > x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}

• // OJ: https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int findBestValue(vector<int>& A, int target) {
sort(begin(A), end(A));
vector<int> sum = A;
partial_sum(begin(sum), end(sum), begin(sum));
int N = A.size(), L = 0, R = A.back(), minDiff = INT_MAX, ans = R;
while (L <= R) {
int M = (L + R) / 2;
int i = lower_bound(begin(A), end(A), M) - begin(A);
int total = (i - 1 >= 0 ? sum[i - 1] : 0) + (N - i) * M;
int diff = abs(total - target);
if (diff <= minDiff) {
if (diff < minDiff) ans = M;
else ans = min(ans, M);
minDiff = diff;
}
if (total >= target) R = M - 1;
else L = M + 1;
}
return ans;
}
};

• class Solution:
def findBestValue(self, arr: List[int], target: int) -> int:
arr.sort()
s = list(accumulate(arr, initial=0))
ans, diff = 0, inf
for value in range(max(arr) + 1):
i = bisect_right(arr, value)
d = abs(s[i] + (len(arr) - i) * value - target)
if diff > d:
diff = d
ans = value
return ans


• func findBestValue(arr []int, target int) (ans int) {
sort.Ints(arr)
n := len(arr)
s := make([]int, n+1)
mx := 0
for i, x := range arr {
s[i+1] = s[i] + x
mx = max(mx, x)
}
diff := 1 << 30
for value := 0; value <= mx; value++ {
i := sort.SearchInts(arr, value+1)
d := abs(s[i] + (n-i)*value - target)
if diff > d {
diff = d
ans = value
}
}
return
}

func abs(x int) int {
if x < 0 {
return -x
}
return x
}

func max(a, b int) int {
if a > b {
return a
}
return b
}