Solution: Sum of Mutated Array Closest to Target

Let's solve the Sum of Mutated Array Closest to Target problem using the Sort and Search pattern.

We'll cover the following

Statement

Given an integer array arr and a target value target, find an integer value such that if all the numbers in arr greater than value are replaced with a value, the sum of the array gets as close as possible to the target.

Choose the smaller value if there’s a tie (two value options are equally close to the targe).

Note: The answer doesn’t have to be a number from the array.

Constraints:

  • 1≤1 \leqarr.length ≤103 \leq 10^3

  • 1≤1 \leqarr[i], target ≤104\leq 10^4

Solution

We begin by sorting the array in ascending order, which ensures that smaller numbers are evaluated first. Then, we evaluate whether replacing all subsequent numbers with the current number would minimize the gap between the modified array sum and the target for each number in the array. We maintain the remaining target to determine if replacing all subsequent numbers with the current value would minimize the gap. Initially, the remaining target is equal to the original target value. As we traverse the array, we subtract each processed number from the target to update the remaining target. This running total helps us evaluate how much more is needed to match the target. At each step, we check if the remaining target is small enough to be achieved by replacing all the remaining numbers in the array with the current number. This is calculated as follows:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.