# 1300. Sum of Mutated Array Closest to Target

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`

``````class Solution {
public:
int findBestValue(vector<int>& arr, int target) {
int n = arr.size(), left = 0, right = target;
while (left < right) {
int mid = left + (right - left) / 2;
if (diff(mid, arr, target) > diff(mid + 1, arr, target)) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
int diff(int mid, vector<int>& arr, int target) {
int sum = 0;
for (int num : arr) {
sum += min(num, mid);
}
return abs(sum - target);
}
};
``````

``````class Solution {
public:
int findBestValue(vector<int>& arr, int target) {
int n = arr.size(), i = 0;
sort(arr.begin(), arr.end());
while (i < n && target > arr[i] * (n - i)) {
target -= arr[i++];
}
if (i == n) return arr[n - 1];
int res = target / (n - i);
if (target - res * (n - i) > (res + 1) * (n - i) - target) {
++res;
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1300

https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/

https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/discuss/463306/JavaC%2B%2BPython-Just-Sort-O(nlogn)

https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/discuss/470114/C%2B%2B-binary-search-%2B-get-the-lowest-point

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation