1300. Sum of Mutated Array Closest to Target LeetCode Solution

In this guide, you will get 1300. Sum of Mutated Array Closest to Target LeetCode Solution with the best time and space complexity. The solution to Sum of Mutated Array Closest to Target problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Sum of Mutated Array Closest to Target solution in C++
  4. Sum of Mutated Array Closest to Target solution in Java
  5. Sum of Mutated Array Closest to Target solution in Python
  6. Additional Resources
1300. Sum of Mutated Array Closest to Target LeetCode Solution image

Problem Statement of Sum of Mutated Array Closest to Target

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 <= 104
1 <= arr[i], target <= 105

Complexity Analysis

  • Time Complexity: O(\texttt{sort})
  • Space Complexity: O(\texttt{sort})
See also  368. Largest Divisible Subset LeetCode Solution

1300. Sum of Mutated Array Closest to Target LeetCode Solution in C++

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();
  }
};
/* code provided by PROGIEZ */

1300. Sum of Mutated Array Closest to Target LeetCode Solution in Java

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];
  }
}
// code provided by PROGIEZ

1300. Sum of Mutated Array Closest to Target LeetCode Solution in Python

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]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: