Sum of Mutated Array Closest to Target - Practice Coding Problems

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 necessarily a number from arr.

Input & Output

Example 1 — Basic Case

$ Input: arr = [4,9,3], target = 10

› Output: 3

💡 Note: When value = 3: [min(4,3), min(9,3), min(3,3)] = [3,3,3], sum = 9. When value = 4: sum = 11. Both |9-10|=1 and |11-10|=1, so return minimum value = 3.

Example 2 — Exact Target

$ Input: arr = [2,3,5], target = 10

› Output: 5

💡 Note: When value = 5: no elements change since all ≤ 5, sum = 2+3+5 = 10 = target exactly.

Example 3 — Small Target

$ Input: arr = [60864,25176,27249,21296,64451,35928,53067,25101,77699], target = 4

› Output: 0

💡 Note: Target is very small, so optimal value is 0 (makes all elements 0), giving sum closest to 4.

Constraints

1 ≤ arr.length ≤ 10⁴
1 ≤ arr[i], target ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array [4,9,3] and target 10

Process

Test different mutation values to find closest sum

Output

Return value 3 that gives sum closest to target

Key Takeaway

🎯 Key Insight: The sum is monotonic in the mutation value - binary search can efficiently find the optimal point

Asked in

G Google 25 a Amazon 18 f Facebook 12 M Microsoft 10

The key insight is that the sum function is monotonic - as the mutation value increases, the sum increases. This allows us to use binary search on the answer space to efficiently find the optimal value. Time: O(n log max_val), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Possible Values	O(n * max_val)	O(1)	Try every possible mutation value from 0 to max(arr) and find the one closest to target
Binary Search on Answer Space	O(n log max_val)	O(1)	Binary search on the possible mutation values to find optimal answer efficiently
Sort + Prefix Sum Optimization	O(n²)	O(1)	Sort array first, then use prefix sums to efficiently calculate mutation results

Brute Force - Try All Possible Values — Algorithm Steps

Step 1: Find the range [0, max(arr)] of possible mutation values
Step 2: For each value in range, calculate sum after mutation
Step 3: Track the value that gives sum closest to target

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Find range [0, max(arr)] to test

Test Each Value

For each value, calculate sum after mutation

Track Best

Keep the value giving sum closest to target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* arr, int arrSize, int target) {
    int bestVal = 0;
    int bestDiff = INT_MAX;
    
    // Find max value in array
    int maxVal = 0;
    for (int i = 0; i < arrSize; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    
    // Try all possible values from 0 to max(arr)
    for (int val = 0; val <= maxVal; val++) {
        // Calculate sum after mutation
        int currentSum = 0;
        for (int i = 0; i < arrSize; i++) {
            currentSum += (arr[i] < val) ? arr[i] : val;
        }
        
        int diff = abs(currentSum - target);
        
        // Update best if closer to target (or same distance but smaller val)
        if (diff < bestDiff || (diff == bestDiff && val < bestVal)) {
            bestDiff = diff;
            bestVal = val;
        }
    }
    
    return bestVal;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int arr[100];
    int arrSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            arr[arrSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int target;
    scanf("%d", &target);
    
    printf("%d\n", solution(arr, arrSize, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n * max_val)

For each of max_val possible mutation values, we iterate through array of size n

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track best result

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Possible Values — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler