1300. Sum of Mutated Array Closest to Target
Description
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
Solutions
Solution 1: Sorting + Prefix Sum + Binary Search + Enumeration
We notice that the problem requires changing all values greater than value
to value
and then summing them up. Therefore, we can consider sorting the array arr
first, and then calculating the prefix sum array $s$, where $s[i]$ represents the sum of the first $i$ elements of the array.
Next, we can enumerate all value
values from smallest to largest. For each value
, we can use binary search to find the index $i$ of the first element in the array that is greater than value
. At this point, the number of elements in the array greater than value
is $n - i$, so the number of elements in the array less than or equal to value
is $i$. The sum of the elements in the array less than or equal to value
is $s[i]$, and the sum of the elements in the array greater than value
is $(n - i) \times value$. Therefore, the sum of all elements in the array is $s[i] + (n - i) \times \textit{value}$. If the absolute difference between $s[i] + (n - i) \times \textit{value}$ and target
is less than the current minimum difference diff
, update diff
and ans
.
After enumerating all value
values, we can get the final answer ans
.
Time complexity $O(n \times \log n)$, space complexity $O(n)$. Where $n$ is the length of the array arr
.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|