Sum of Mutated Array Closest to Target

Medium
1375.

Sum of Mutated Array Closest to Target

Sum of Mutated Array Closest to Target is a medium coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.

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^4
  • 1 <= arr[i], target <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var findBestValue = function(arr, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • 1 <= arr[i], target <= 10^5

Hints for Sum of Mutated Array Closest to Target

  1. Hint 1

    As value grows, the capped sum never decreases — it is a monotone function of value.

  2. Hint 2

    Values above max(arr) change nothing, so the search range is [0, max(arr)].

  3. Hint 3

    Binary-search the smallest value whose capped sum reaches target; 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

  1. Let hi = max(arr). If S(hi) < target, no cap reaches the target and hi (the smallest value giving the full sum) is the answer.
  2. Otherwise binary-search the smallest v in [1, hi] with S(v) >= target.
  3. Compare target - S(v - 1) with S(v) - target; return v - 1 when it is not larger (the tie goes to the smaller value), otherwise v.

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 lo

Java

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