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 <= 1041 <= arr[i], target <= 105The brute force approach involves iterating over all possible values from 1 to the maximum element in the array. For each value, replace larger numbers in the array and calculate the sum of the array. Track and update the closest sum to the target.
This solution iterates over a range of possible values and adjusts the array values to calculate the sum. The closest value is determined by minimizing the absolute difference between the calculated sum and the target.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * maxValue), Space Complexity: O(1)
Start by sorting the array and using binary search to find the smallest value where adjusting elements results in the sum being as close as possible to the target. This is more efficient than the brute force approach.
The C solution uses binary search to efficiently determine the value that minimizes the sum difference from the target by dynamically reducing the search space.
C++
Java
Python
C#
JavaScript
Time Complexity: O(nlogn), Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * maxValue), Space Complexity: O(1) |
| Binary Search Approach | Time Complexity: O(nlogn), Space Complexity: O(1) |
Target Sum - Dynamic Programming - Leetcode 494 - Python • NeetCode • 204,471 views views
Watch 9 more video solutions →Practice Sum of Mutated Array Closest to Target with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor