You are given an integer array arr and an integer target. You can "mutate" the array by replacing every element in arr that is greater than or equal to some integer value value with value itself. Your goal is to choose a value such that the sum of the mutated array is as close as possible to target. If there are multiple answers, return the smallest such value.
arr can be replaced at most once, and only if it's greater than or equal to value.value remain unchanged.
Example:
arr = [2,3,5], target = 10
If you choose value = 5, the array remains the same and the sum is 10.
At first glance, one might consider trying every possible value from 1 up to the maximum element in arr, mutate the array each time, and check which sum is closest to target. However, this brute-force approach is inefficient, especially for large arrays or large values.
We can observe that increasing value will never increase the sum of the mutated array, because more elements are being capped at a lower number. This monotonicity suggests that binary search could be effective. Instead of checking all possible value values, we can efficiently "zoom in" on the optimal one.
The key insight is to realize that for a given value, the mutated sum can be computed quickly, and that the function mapping value to mutated sum is non-increasing. So, we can use binary search to find the smallest value that gets us closest to target.
value, mutate each element in arr by replacing it with value if it is greater than value. The mutated sum is the sum of all mutated elements.
value decreases, we can use binary search on value in the range [1, max(arr)] to find the value that makes the mutated sum closest to target.
value, iterate through arr, sum each element as-is if it is less than value, or add value otherwise.
value that produces the sum with the smallest absolute difference to target. If there is a tie, prefer the smaller value.
value that yields the closest mutated sum.
This approach is much more efficient than brute force, as it reduces the search space from potentially thousands of values to at most log(max(arr)) iterations.
Let's use arr = [2, 3, 5] and target = 10.
value can be from 1 to 5.
value = 5.
The binary search will efficiently narrow down to value = 5 as the answer.
value from 1 to max(arr), compute the mutated sum (O(n) per value). This leads to O(n * max(arr)) time.
value (O(log(max(arr)))) and for each, compute the mutated sum (O(n)). So overall O(n log(max(arr))) time.
By recognizing the monotonic relationship between the mutation value and the mutated sum, we can use binary search to efficiently find the best value that brings the sum closest to the target. The approach is both elegant and performant, reducing a potentially expensive brute-force search to a fast, logarithmic one. This problem is a great example of how understanding the properties of a function (in this case, monotonicity) can lead to a dramatic optimization.
class Solution:
def findBestValue(self, arr, target):
def mutated_sum(value):
return sum(min(x, value) for x in arr)
left, right = 0, max(arr)
closest, answer = float('inf'), 0
while left <= right:
mid = (left + right) // 2
curr_sum = mutated_sum(mid)
diff = abs(curr_sum - target)
if diff < closest or (diff == closest and mid < answer):
closest = diff
answer = mid
if curr_sum < target:
left = mid + 1
else:
right = mid - 1
return answer
class Solution {
public:
int findBestValue(vector<int>& arr, int target) {
auto mutated_sum = [&](int value) {
int sum = 0;
for (int x : arr) sum += std::min(x, value);
return sum;
};
int left = 0, right = *max_element(arr.begin(), arr.end());
int closest = INT_MAX, answer = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
int curr_sum = mutated_sum(mid);
int diff = abs(curr_sum - target);
if (diff < closest || (diff == closest && mid < answer)) {
closest = diff;
answer = mid;
}
if (curr_sum < target)
left = mid + 1;
else
right = mid - 1;
}
return answer;
}
};
class Solution {
public int findBestValue(int[] arr, int target) {
int left = 0, right = 0;
for (int x : arr) right = Math.max(right, x);
int closest = Integer.MAX_VALUE, answer = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
int currSum = 0;
for (int x : arr) currSum += Math.min(x, mid);
int diff = Math.abs(currSum - target);
if (diff < closest || (diff == closest && mid < answer)) {
closest = diff;
answer = mid;
}
if (currSum < target)
left = mid + 1;
else
right = mid - 1;
}
return answer;
}
}
var findBestValue = function(arr, target) {
const mutatedSum = value => arr.reduce((sum, x) => sum + Math.min(x, value), 0);
let left = 0, right = Math.max(...arr);
let closest = Infinity, answer = 0;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
let currSum = mutatedSum(mid);
let diff = Math.abs(currSum - target);
if (diff < closest || (diff === closest && mid < answer)) {
closest = diff;
answer = mid;
}
if (currSum < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
};