# 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.

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

# Solution

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)

Approach 1:

    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)

Approach 2:

    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++)

Approach 1:

Approach 2: