We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Mutated Array Closest to Target

Number: 1232

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an integer array arr and a target, find an integer value such that when every element in arr greater than value is replaced with value, the sum of the array is as close as possible (in absolute difference) to target. In the event of a tie, return the smallest such value. Note that the returned value is not necessarily an element of arr.

Key Insights

  • Sorting the array simplifies computation by grouping values and enabling efficient prefix sum calculations.
  • A binary search can be employed over the range of possible values (from 0 to the maximum element in arr) to determine the optimal mutation value.
  • Precomputed prefix sums allow quick determination of the mutated sum for each candidate value.
  • Care must be taken to handle tie cases by preferring the smaller candidate.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting and binary search evaluation. Space Complexity: O(n) for storing prefix sums.

Solution

The solution first sorts the input array and calculates prefix sums to enable fast sum queries. Then, it uses binary search between 0 and the maximum element in the array to find the candidate value that, when used to cap the array’s values, minimizes the absolute difference between the mutated sum and the target. For any given candidate value, the prefix sum array quickly computes the sum of all elements less than or equal to the candidate, and the remainder of the sum is computed by multiplying the candidate by the count of larger elements. The candidate with the smallest difference is returned, resolving ties by choosing the smaller candidate.

Code Solutions

def find_best_value(arr, target):
    # Sort the array to simplify the prefix sum and binary search steps
    arr.sort()
    n = len(arr)
    # Create prefix sums so that prefix[i] is the sum of first i elements
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]
    
    def compute_sum(val):
        # Find first index in arr where value > val using binary search
        lo, hi = 0, n
        while lo < hi:
            mid = (lo + hi) // 2
            if arr[mid] > val:
                hi = mid
            else:
                lo = mid + 1
        # Sum is sum of elements <= val plus (count of elements > val) * val
        return prefix[lo] + (n - lo) * val
    
    lo, hi = 0, arr[-1]
    best_val = hi
    best_diff = float('inf')
    
    # Binary search for the optimal mutation value
    while lo <= hi:
        mid = (lo + hi) // 2
        current_sum = compute_sum(mid)
        current_diff = abs(current_sum - target)
        
        if current_diff < best_diff or (current_diff == best_diff and mid < best_val):
            best_val = mid
            best_diff = current_diff
        
        if current_sum < target:
            lo = mid + 1
        else:
            hi = mid - 1
            
    return best_val

# Example usage:
print(find_best_value([4, 9, 3], 10))  # Output: 3
← Back to All Questions