Sum of Mutated Array Closest to Target — Problem & Solution
Sum of Mutated Array Closest to Target solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Sum of Mutated Array Closest to Target is a medium coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Binary Search
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Pick a non-negative integer value. Every element of arr that is greater than value is lowered to value; the others stay as they are. This gives a capped sum for that value.
Return the value whose capped sum is closest to target (smallest absolute difference). If two values tie, return the smaller one.
value does not have to be an element of arr — it may even be 0.
Example 1
Input: arr = [6,2,9], target = 12
Output: 5
Explanation: Capping at 5 gives 5 + 2 + 5 = 12 exactly.
Example 2
Input: arr = [1,1,1], target = 1
Output: 0
Explanation: Capping at 0 gives 0 (off by 1); capping at 1 gives 3 (off by 2).
Example 3
Input: arr = [3,8,5], target = 30
Output: 8
Explanation: Even uncapped the sum is 16, and any value of 8 or more gives that sum — 8 is the smallest.
Constraints
1 <= arr.length <= 10^41 <= arr[i], target <= 10^5
Hints for Sum of Mutated Array Closest to Target
Hint 1
As
valuegrows, the capped sum never decreases — it is a monotone function ofvalue.Hint 2
Values above
max(arr)change nothing, so the search range is[0, max(arr)].Hint 3
Binary-search the smallest
valuewhose capped sum reachestarget; the answer is that value or the one just below it.
How to solve Sum of Mutated Array Closest to Target
The capped sum S(v) = Σ min(arr[i], v) is strictly increasing on [0, max(arr)], so the point where it crosses target can be binary-searched, and the closest sum sits on one side of the crossing or the other.
Approach
- Let
hi = max(arr). IfS(hi) < target, no cap reaches the target andhi(the smallest value giving the full sum) is the answer. - Otherwise binary-search the smallest
vin[1, hi]withS(v) >= target. - Compare
target - S(v - 1)withS(v) - target; returnv - 1when it is not larger (the tie goes to the smaller value), otherwisev.
Why it works
Raising v by one adds one for every element that is at least v, so S strictly increases until v reaches the maximum and is flat afterwards. Every u < v - 1 has S(u) < S(v - 1) < target, so it is farther from the target than v - 1; every u > v has S(u) >= S(v) >= target, so it is no closer than v and loses ties as the larger value. Only v - 1 and v remain.
Complexity
- Time —
O(n log M) with M = max(arr) - Space —
O(1)
Pitfalls
- The answer can be 0 when the array is long and the target is tiny — start the range at 0, not at 1 or
min(arr). - On a tie the smaller value wins.
- If the full sum is below the target, the answer is
max(arr), not some larger number.
Reference solution
Python
from typing import List
def findBestValue(arr: List[int], target: int) -> int:
def capped(v):
return sum(a if a < v else v for a in arr)
hi = max(arr)
if capped(hi) < target:
return hi
lo = 1
while lo < hi:
mid = (lo + hi) // 2
if capped(mid) >= target:
hi = mid
else:
lo = mid + 1
below = target - capped(lo - 1)
above = capped(lo) - target
return lo - 1 if below <= above else loJava
public static int findBestValue(int[] arr, int target) {
int hi = 0;
for (int a : arr) hi = Math.max(hi, a);
if (cappedSum(arr, hi) < target) return hi;
int lo = 1;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (cappedSum(arr, mid) >= target) hi = mid; else lo = mid + 1;
}
int below = target - cappedSum(arr, lo - 1);
int above = cappedSum(arr, lo) - target;
return below <= above ? lo - 1 : lo;
}
static int cappedSum(int[] arr, int v) {
int s = 0;
for (int a : arr) s += Math.min(a, v);
return s;
}C++
int cappedSum(const vector<int>& arr, int v) {
int s = 0;
for (int a : arr) s += min(a, v);
return s;
}
int findBestValue(vector<int>& arr, int target) {
int hi = *max_element(arr.begin(), arr.end());
if (cappedSum(arr, hi) < target) return hi;
int lo = 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (cappedSum(arr, mid) >= target) hi = mid; else lo = mid + 1;
}
int below = target - cappedSum(arr, lo - 1);
int above = cappedSum(arr, lo) - target;
return below <= above ? lo - 1 : lo;
}JavaScript
var findBestValue = function(arr, target) {
var capped = function(v) {
var s = 0;
for (var i = 0; i < arr.length; i++) s += arr[i] < v ? arr[i] : v;
return s;
};
var hi = 0;
for (var i = 0; i < arr.length; i++) if (arr[i] > hi) hi = arr[i];
if (capped(hi) < target) return hi;
var lo = 1;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (capped(mid) >= target) hi = mid; else lo = mid + 1;
}
var below = target - capped(lo - 1);
var above = capped(lo) - target;
return below <= above ? lo - 1 : lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms