Sum of Mutated Array Closest to Target

• Initialize min_diff to a very large value and result to -1.
• Iterate through every possible candidate for value from 0 up to a safe upper bound (e.g., 100001, based on problem constraints).
• For each candidate v:
  • Calculate the sum of the mutated array, let's call it current_sum. To do this, iterate through the input arr and for each number num, add min(num, v) to current_sum.
  • Compute the absolute difference diff = abs(current_sum - target).
  • If diff is smaller than min_diff, it means we've found a better value. Update min_diff = diff and result = v.
  • Because we are iterating v in increasing order, the first time we find a value that gives the minimum possible difference, it will be the smallest such value, automatically handling the tie-breaking rule.
• After checking all candidates, return result.

The problem asks us to find an integer value that minimizes the absolute difference between the sum of a mutated array and a target. The mutated array is formed by replacing all elements in the original array that are larger than value with value itself.

A straightforward way to solve this is to perform an exhaustive search. We need to determine the search space for value. The smallest possible value is 0. The largest effective value would be the maximum element in the array, but to be safe, we can set an upper bound based on the constraints, such as 100001 (since target and arr[i] are at most 10^5).

We iterate through each integer v in this range [0, 100001]. For each v, we calculate the sum of the mutated array by iterating through arr and adding Math.min(num, v) for each element num. Then, we calculate the absolute difference between this sum and the target. We maintain a variable min_diff to store the minimum difference found so far and result to store the corresponding value. If we find a v that yields a smaller difference, we update min_diff and result. Since we iterate v from smallest to largest, the first value we find for a given minimum difference will be the smallest one, satisfying the tie-breaker condition.

1class Solution {2    public int findBestValue(int[] arr, int target) {3        int minDiff = Integer.MAX_VALUE;4        int result = -1;5        // A safe upper bound from constraints (max of arr[i] and target is 10^5)6        int maxVal = 100001; 7 8        for (int v = 0; v <= maxVal; v++) {9            long currentSum = 0;10            for (int num : arr) {11                currentSum += Math.min(num, v);12            }13 14            int diff = Math.abs((int)currentSum - target);15 16            if (diff < minDiff) {17                minDiff = diff;18                result = v;19            }20        }21        return result;22    }23}

• Define a helper function getSum(v, arr) that takes a value v and the array arr, and returns the sum of the mutated array. This function iterates through arr and sums up min(num, v) for each num.
• The function getSum(v, arr) is monotonically non-decreasing with respect to v.
• We can use binary search on the possible answer value. The search space for value is from 0 to a safe upper bound like 100001.
• Initialize low = 0, high = 100001.
• While low <= high:
  • Calculate mid = low + (high - low) / 2.
  • Compute current_sum = getSum(mid, arr).
  • If current_sum < target, it means mid is too small to reach the target, so we need to try larger values. We set low = mid + 1.
  • If current_sum >= target, mid might be the answer or it might be too large. We try smaller values by setting high = mid - 1.
• The loop terminates when low > high. The optimal integer value must be one of high or low (the two values surrounding the point where the sum crosses the target).
• Calculate the sum for high and low, find their absolute differences from target, and return the value that gives the smaller difference. If the differences are equal, return the smaller value (high).

Instead of a linear scan, we can significantly speed up the search for the optimal value by using binary search. The search space for value is still the range of integers from 0 to an upper bound like 100001.

Let's define a function getSum(v) that computes the sum of the array when all elements larger than v are replaced by v. This function is monotonic: if v1 < v2, then getSum(v1) <= getSum(v2). This allows us to apply binary search.

We binary search for value in the range [0, 100001]. In each step, we take the middle element mid as a candidate value, compute getSum(mid), and compare it to target.

• If getSum(mid) is less than target, we know that mid and all values smaller than it will result in a sum that is even further from target on the lower side. So, we need to explore larger values by setting low = mid + 1.
• If getSum(mid) is greater than or equal to target, mid could be a potential answer, but a smaller value might give a sum that is also close to target. We explore smaller values by setting high = mid - 1.

This binary search will not necessarily land on the exact best value, but it will narrow the possibilities down to two candidates. When the loop terminates (low > high), the best value is guaranteed to be either low or high. We can then compute getSum(low) and getSum(high), compare their absolute differences to target, and choose the one that results in a smaller difference. In case of a tie, we choose the smaller value, which will be high.

1class Solution {2    public int findBestValue(int[] arr, int target) {3        int low = 0;4        // A safe upper bound from constraints5        int high = 100001;6        int ans = 0;7 8        while (low <= high) {9            int mid = low + (high - low) / 2;10            long sum = getSum(arr, mid);11            if (sum < target) {12                low = mid + 1;13            } else {14                high = mid - 1;15            }16        }17 18        // After the loop, low and high are the best candidates.19        // Let's check which one is closer to the target.20        long sumLow = getSum(arr, high);21        long sumHigh = getSum(arr, low);22 23        if (Math.abs(sumLow - target) <= Math.abs(sumHigh - target)) {24            return high;25        } else {26            return low;27        }28    }29 30    private long getSum(int[] arr, int value) {31        long sum = 0;32        for (int num : arr) {33            sum += Math.min(num, value);34        }35        return sum;36    }37}

• First, sort the input array arr in non-decreasing order.
• Initialize a prefix_sum to 0. This will store the sum of elements we have processed so far.
• Iterate through the sorted array from i = 0 to n-1.
  • At each index i, calculate the number of remaining elements: remaining_count = n - i.
  • Consider the sum if we were to cap all remaining elements at the current value arr[i]. This sum would be prefix_sum + remaining_count * arr[i].
  • If this potential sum is greater than or equal to target, it means the ideal value is less than or equal to arr[i] and greater than arr[i-1]. We have found the correct segment to search for the answer.
  • The ideal (possibly fractional) value that would make the sum exactly target is (target - prefix_sum) / remaining_count.
  • We need to find the best integer value. The best integer is the one closest to this ideal fractional value. We can find this by checking the integers v_low = (target - prefix_sum) / remaining_count (integer division) and v_high = v_low + 1.
  • Calculate the sums for v_low and v_high and return the one that gives a sum closer to target. If differences are equal, v_low is chosen as it's smaller.
  • Once the best value is found and returned, the algorithm terminates.
• If the loop finishes without returning, it means target is larger than the sum of the original array. The closest we can get is the original sum, which is achieved by any value >= arr[n-1]. The minimum such value is arr[n-1], so we return it.

By sorting the array arr, we can process elements in a structured way. The core idea is that for any chosen value, all elements in arr smaller than value will contribute their original value to the sum, while all elements larger than value will contribute value to the sum.

Let's iterate through the sorted array and maintain a prefix_sum of the elements we've passed. At index i, prefix_sum holds the sum of arr[0] through arr[i-1]. The remaining n-i elements are arr[i], ..., arr[n-1]. If we were to choose a value such that arr[i-1] < value <= arr[i], the total sum would be prefix_sum + (n-i) * value.

We want this sum to be as close as possible to target. We can find an ideal (potentially fractional) value by solving prefix_sum + (n-i) * value = target, which gives value = (target - prefix_sum) / (n-i).

Our algorithm iterates through the sorted array. At each index i, we check if the target can be achieved by a value <= arr[i]. This is true if target <= prefix_sum + (n-i) * arr[i]. Once this condition is met, we've located the segment where the optimal value lies. We then calculate the ideal value as described above. Since the answer must be an integer, the best candidates are the two integers surrounding the ideal fractional value. We check these two integers, see which one produces a sum closer to target, and return it, respecting the tie-breaking rule.

If the loop completes, it means the target is larger than the sum of the original array. The best we can do is not mutate the array at all. The minimum value to achieve this is the largest element in the array, arr[n-1].

1import java.util.Arrays;2 3class Solution {4    public int findBestValue(int[] arr, int target) {5        Arrays.sort(arr);6        int n = arr.length;7        long prefixSum = 0;8 9        for (int i = 0; i < n; i++) {10            long remainingCount = n - i;11            // Check if the target is achievable with a value <= arr[i]12            if (prefixSum + remainingCount * arr[i] >= target) {13                // The ideal value is in the range (arr[i-1], arr[i]]14                // (or [0, arr[0]] for i=0)15                long valueLow = (target - prefixSum) / remainingCount;16                long valueHigh = valueLow + 1;17 18                long sumLow = prefixSum + remainingCount * valueLow;19                long sumHigh = prefixSum + remainingCount * valueHigh;20 21                if (Math.abs(target - sumLow) <= Math.abs(target - sumHigh)) {22                    return (int) valueLow;23                } else {24                    return (int) valueHigh;25                }26            }27            prefixSum += arr[i];28        }29 30        // If target is greater than the total sum of the array31        return arr[n - 1];32    }33}