Skip to content

1300. Sum of Mutated Array Closest to Target 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int findBestValue(vector<int>& arr, int target) {
    const int n = arr.size();
    const double err = 1e-9;

    int prefix = 0;

    ranges::sort(arr);

    for (int i = 0; i < n; ++i) {
      int ans = round((target - prefix - err) / (double)(n - i));
      if (ans <= arr[i])
        return ans;
      prefix += arr[i];
    }

    return arr.back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int findBestValue(int[] arr, int target) {
    final int n = arr.length;
    final double err = 1e-9;

    int prefix = 0;

    Arrays.sort(arr);

    for (int i = 0; i < n; ++i) {
      int ans = (int) Math.round(((float) target - prefix - err) / (n - i));
      if (ans <= arr[i])
        return ans;
      prefix += arr[i];
    }

    return arr[n - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def findBestValue(self, arr: List[int], target: int) -> int:
    prefix = 0

    arr.sort()

    for i, a in enumerate(arr):
      ans = round((target - prefix) / (len(arr) - i))
      if ans <= a:
        return ans
      prefix += a

    return arr[-1]