Is Sum of Mutated Array Closest to Target easy or hard?

This problem is classified as Medium. The challenge is recognizing that the mutation value creates a monotonic relationship between the chosen value and the resulting array sum. Once that observation is made, binary search becomes a natural solution.

Sum of Mutated Array Closest to Target Python/Java solution

Implement binary search on the value range from 0 to max(arr). For each midpoint, compute the mutated sum using min(num, mid) for every element. Compare the result with the target and adjust the search boundaries until the closest value is found. The same logic works in Python, Java, C++, and other languages.

How to solve Sum of Mutated Array Closest to Target in O(n)?

A strict O(n) solution is generally not achievable because the correct mutation value must be searched within a numeric range. Binary search over that range is the standard technique, resulting in O(n log m) complexity. Some optimizations using sorting and prefix sums reduce repeated work but still involve logarithmic search.

What is the best approach for Sum of Mutated Array Closest to Target?

Binary search on the mutation value is the most efficient approach. The possible value range is from 0 to the maximum element in the array, and the resulting array sum increases monotonically as the value increases. This property allows binary search to find the value that produces a sum closest to the target in O(n log m) time.

Is Sum of Mutated Array Closest to Target asked at Google/Amazon/Meta?

This problem follows a pattern commonly used in interviews at companies like Google and Amazon: binary search on the answer. Variants of the problem appear in coding interviews where you must search a numeric range and evaluate a condition with each guess.

What data structure is used in Sum of Mutated Array Closest to Target?

The primary data structure is a simple array. The algorithm relies on binary search over a value range and repeatedly iterates through the array to compute the mutated sum. Some optimized solutions also sort the array and use prefix sums for faster calculations.

What is the time complexity of Sum of Mutated Array Closest to Target?

The optimal solution runs in O(n log m) time, where n is the array length and m is the maximum value in the array. Each binary search step computes the mutated sum by iterating through the array once. Space complexity remains O(1) since only a few variables are used.

Description Hints 3 Solution Video 11:38

1300. Sum of Mutated Array Closest to Target

Medium46.8% acceptance2 companies

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 <= 10⁴
1 <= arr[i], target <= 10⁵

Asked at 2 companies

Google Bloomberg

Topics

Hints open one at a time

Hint 1

If you draw a graph with the value on one axis and the absolute difference between the target and the array sum, what will you get?

Hint 2

That graph is uni-modal.

Hint 3

Use ternary search on that graph to find the best value.

11:38

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def findBestValue(self, arr: List[int], target: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[4,9,3]
10

Input

[2,3,5]
10

Input

[60864,25176,27249,21296,20204]
56803

Your code is saved on this device.Solution