1300. Sum of Mutated Array Closest to Target #

Problem #

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 <= 10^4
• 1 <= arr[i], target <= 10^5

Problem Summary #

Given an integer array arr and a target value target, return an integer value such that after changing all values in the array greater than value to value, the sum of the array is closest to target (closest means the absolute difference between the two is minimized). If there are multiple solutions that make the sum closest to target, return the minimum integer among them. Note that the answer is not necessarily a number in arr.

Note:

• 1 <= arr.length <= 10^4
• 1 <= arr[i], target <= 10^5

Solution Approach #

• Given an array arr and target. Can we find a value such that after changing all values in the array greater than value to value, the sum of the array is closest to target? If there are multiple methods, output the smallest value.
• This problem can be solved with binary search. The final unique answer has 2 constraints: one is that the mutated array sum is closest to target. The other is that the output value is the minimum among all possible methods. Binary search for the final value. mid is the value being tried; each time mid is chosen, compute the total sum once and compare it with target. Since each number in the array has a different gap from mid, each adjustment of mid may result in mid being too small and the distance to target instead becoming larger; or mid being too large and the distance to target instead becoming smaller. The solution here is to take the possible values above and below value and compare them.

Code #

func findBestValue(arr []int, target int) int {
	low, high := 0, 100000
	for low < high {
		mid := low + (high-low)>>1
		if calculateSum(arr, mid) < target {
			low = mid + 1
		} else {
			high = mid
		}
	}
	if high == 100000 {
		res := 0
		for _, num := range arr {
			if res < num {
				res = num
			}
		}
		return res
	}
	// Compare how close to target it is when the threshold line is set at left - 1 and left respectively
	sum1, sum2 := calculateSum(arr, low-1), calculateSum(arr, low)
	if target-sum1 <= sum2-target {
		return low - 1
	}
	return low
}

func calculateSum(arr []int, mid int) int {
	sum := 0
	for _, num := range arr {
		sum += min(num, mid)
	}
	return sum
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}