{x}
blog image

Sum of Mutated Array Closest to Target

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

 

Example 1:

Input: arr = [4,9,3], target = 10
Output: 3
Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.

Example 2:

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

Example 3:

Input: arr = [60864,25176,27249,21296,20204], target = 56803
Output: 11361

 

Constraints:

  • 1 <= arr.length <= 104
  • 1 <= arr[i], target <= 105

Solution Explanation:

This problem asks to find a value such that when all elements in the input array greater than this value are replaced with this value, the sum of the array is closest to the target value. The solution employs a combination of sorting, prefix sums, binary search, and enumeration for efficient computation.

Approach:

  1. Sorting: The input array arr is sorted in ascending order. This enables efficient calculation of prefix sums and binary search later on.

  2. Prefix Sums: A prefix sum array s is calculated. s[i] stores the sum of elements from arr[0] to arr[i-1]. This allows for quick computation of the sum of a subarray.

  3. Enumeration and Binary Search: The code iterates through possible values (value) from 0 up to the maximum element in arr. For each value:

    • A binary search (bisect_right in Python, upper_bound in C++, sort.SearchInts in Go, or custom search function in Java) finds the index i where elements greater than value begin.
    • The sum of elements less than or equal to value is s[i].
    • The sum of elements greater than value is (len(arr) - i) * value.
    • The total sum with the replacement is calculated as s[i] + (len(arr) - i) * value.
    • The absolute difference between this sum and the target is computed.
    • The value resulting in the minimum absolute difference is stored as the answer.

  4. Result: The function returns the value that produces the sum closest to the target.

Time Complexity:

  • Sorting the array takes O(n log n) time.
  • Calculating prefix sums takes O(n) time.
  • The loop iterates up to the maximum element in the array (which is at most O(n)). Inside the loop, binary search takes O(log n) time.
  • Therefore, the overall time complexity is dominated by O(n log n) due to sorting.

Space Complexity:

  • The prefix sum array s takes O(n) space.
  • The sorted array (in place sorting is usually done) may use O(n) space in some implementations (not in-place), otherwise, the space complexity is O(1) if we are using in-place sorting.
  • The overall space complexity is O(n).

Code Examples (with detailed comments):

The code snippets in Python, Java, C++, and Go provided in the problem description are well-commented and implement the algorithm as explained above. They differ slightly in syntax and specific functions used for binary search (e.g., bisect_right vs. upper_bound), but the underlying logic remains the same.