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
Solution 1. Binary Answer
// 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.
https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/discuss/463268/JavaC%2B%2B-4ms-binary-search-short-readable-code-%2B-sorting-solution
-
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[0]) 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 }