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:

If the condition above is met, we calculate the replacement value. The replacement value is determined by dividing the remaining target by the number of remaining elements in the array:

We calculate a replacement value instead of simply using the current number because the remaining target may not be an exact multiple of the current number, especially when the remaining target is smaller than current_value×number_of_remaining_elements\text{current\_value} \times \text{number\_of\_remaining\_elements}. This allows us to adjust the replacement value more precisely to minimize the gap between the target and the sum of the modified array.

Now, let’s look at the solution:

  • Sort the array arr in ascending order to make it easier to process elements from smallest to largest.

  • Determine the length of the array, n, to calculate how many elements are left to process at each step.

  • Iterate through the sorted array. For each number num at index i:

    • Check if replacing all remaining numbers (n - i) with a single value can meet or exceed the target.

  • If the target value can be achieved by replacing all remaining elements:

    • Calculate the replacementValue as target / (n - i) (the value needed to meet the target).

    • Choose the lower integer if replacementValue is halfway between two integers (e.g., 3.5).

    • Else, round the candidate value to the nearest integer.

    • Also, return this value as the best replacement.

  • If the target cannot be achieved by replacing all remaining elements, reduce the remainingTarget by subtracting the current number num.

  • Continue processing the remaining elements in the array until the best replacement value is found.

  • If no replacement value is identified during the iteration, the array may already sum as close as possible to the target. In this case, return the maximum value from the array.

Let’s look at the following illustration to get a better understanding of the solution:

Press + to interact
canvasAnimation-image
1 of 6

Let’s look at the code for the solution we just discussed.

import java.util.Arrays;
public class Solution {
    public static int findBestValue(int[] arr, int target) {
        Arrays.sort(arr);
        int n = arr.length;
        int remainingTarget = target;
        for (int i = 0; i < n; i++) {
            int num = arr[i];
            if (remainingTarget <= num * (n - i)) {
                double replacementValue = (double) remainingTarget / (n - i);
                if (replacementValue - (int) replacementValue == 0.5) {
                    return (int) replacementValue;
                }
                return (int) Math.round(replacementValue);
            }
            remainingTarget -= num;
        }
        return arr[n - 1];
    }
    // Helper function to print an array with proper formatting
    private static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(", "); 
            }
        }
        System.out.print("]");
    }
    // Driver code
    public static void main(String[] args) {
        int[][] testCases = {
            {4, 9, 3},       // Example 1: Small array
            {2, 3, 5, 6, 7}, // Example 2: Medium array
            {1, 1, 1, 1},    // Example 3: Uniform array
            {2, 3, 5, 10},   // Example 4: Mixed values
            {1, 2, 23, 24, 34} // Example 5: Larger array
        };
        int[] targets = {10, 17, 4, 13, 110};
        for (int i = 0; i < testCases.length; i++) {
            int[] arr = testCases[i];
            int target = targets[i];
            int value = findBestValue(arr, target);
            System.out.println((i + 1) + ".\tarr: " + Arrays.toString(arr));
            System.out.println("\ttarget: " + target + "\n\n\tvalue: " + value);
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Sum of Mutated Array Closest to Target

Time complexity

The time complexity of the algorithm is O(n logn)O(n \ log n), where nn is the number of elements in the array.

  • Sorting the array: The first step is to sort the array, which takes O(n logn)O(n \ log n).

  • Iterating through the array: The algorithm then iterates through the array once, performing constant-time operations for each element. This contributes O(n)O(n).

As the sorting step dominates, the overall time complexity is O(n logn)O(n \ log n).

Space complexity

The space complexity of the algorithm is O(1)O(1). The algorithm uses only a few integer variables, which occupy constant space.

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