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
Java
-
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; } }
-
// 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; } };
-
print("Todo!")