# 1300. 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.
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.
Input: arr = [2,3,5], target = 10 Output: 5
Input: arr = [60864,25176,27249,21296,20204], target = 56803 Output: 11361
Approach 1: binary search. Find the largest int such that when items capped at it,
sum <= target. Finally needs to compare with
answer + 1. Time:
O(nlogm), where m is max(arr).
Approach 2: sort the array, and for each item, cut it out and find the mean of the rest, to see if the rest can be capped. Time:
O(NlogN) for sort.
# Code (Python)
def findBestValue(self, arr: List[int], target: int) -> int: # idea: binary search. Find the largest int such that when items capped at it, sum <= target. Finally needs to compare with answer + 1 # time: O(nlogm), where m is max(arr) l, r = 0, max(arr) while l < r: m = (l + r) // 2 if self._get_sum(m + 1, arr) <= target: l = m + 1 else: r = m # now l is the largest cap where sum <= target. should compare with l + 1, where sum >= target if abs(self._get_sum(l, arr) - target) <= abs(self._get_sum(l + 1, arr) - target): return l else: return l + 1 def _get_sum(self, cap, nums): return sum(item if item <= cap else cap for item in nums)
def findBestValue(self, arr: List[int], target: int) -> int: # idea: sort the array, and for each item, cut it out and find the mean of the rest, to see if the rest can be capped # time: O(NlogN) for sort # https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/discuss/463586/Python3-Sort-and-scan arr.sort() cut = 0 # total sum being cut out from the cap for i in range(len(arr)): answer = round((target - cut) / (len(arr) - i)) # round() rounds to the nearest integer # if the cap is in effect if answer <= arr[i]: return answer # else the cap is too small, try a bigger one (cut out the next item) else: cut += arr[i] # if target is too large (bigger than sum(arr)), return the smallest possible return arr[-1]
# Code (C++)