# Sum of Mutated Array Closest to Target
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-mutated-array-closest-to-target)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-mutated-array-closest-to-target
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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 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`

# Approaches
## Brute Force Iteration
This approach involves testing every possible integer for the role of `value` within a reasonable range. For each potential `value`, we compute the sum of the transformed array and see how close it is to the `target`. We keep track of the `value` that gives us the smallest difference.
**Time:** O(M * N) - Where N is the number of elements in `arr` and M is the search range for `value` (e.g., 100001). For each of the M possible values, we iterate through the entire array of size N. · **Space:** O(1) - We only use a few variables to store the state, regardless of the input size.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs.
**Cons:** The time complexity is very high, making it impractical for the given constraints. It will likely result in a 'Time Limit Exceeded' error.
### Explanation
The problem asks us to find an integer `value` that minimizes the absolute difference between the sum of a mutated array and a `target`. The mutated array is formed by replacing all elements in the original array that are larger than `value` with `value` itself.

A straightforward way to solve this is to perform an exhaustive search. We need to determine the search space for `value`. The smallest possible `value` is 0. The largest effective `value` would be the maximum element in the array, but to be safe, we can set an upper bound based on the constraints, such as 100001 (since `target` and `arr[i]` are at most 10^5).

We iterate through each integer `v` in this range [0, 100001]. For each `v`, we calculate the sum of the mutated array by iterating through `arr` and adding `Math.min(num, v)` for each element `num`. Then, we calculate the absolute difference between this sum and the `target`. We maintain a variable `min_diff` to store the minimum difference found so far and `result` to store the corresponding `value`. If we find a `v` that yields a smaller difference, we update `min_diff` and `result`. Since we iterate `v` from smallest to largest, the first `value` we find for a given minimum difference will be the smallest one, satisfying the tie-breaker condition.

```java
class Solution {
    public int findBestValue(int[] arr, int target) {
        int minDiff = Integer.MAX_VALUE;
        int result = -1;
        // A safe upper bound from constraints (max of arr[i] and target is 10^5)
        int maxVal = 100001; 

        for (int v = 0; v <= maxVal; v++) {
            long currentSum = 0;
            for (int num : arr) {
                currentSum += Math.min(num, v);
            }

            int diff = Math.abs((int)currentSum - target);

            if (diff < minDiff) {
                minDiff = diff;
                result = v;
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize `min_diff` to a very large value and `result` to -1.
- Iterate through every possible candidate for `value` from 0 up to a safe upper bound (e.g., 100001, based on problem constraints).
- For each candidate `v`:
  - Calculate the sum of the mutated array, let's call it `current_sum`. To do this, iterate through the input `arr` and for each number `num`, add `min(num, v)` to `current_sum`.
  - Compute the absolute difference `diff = abs(current_sum - target)`.
  - If `diff` is smaller than `min_diff`, it means we've found a better `value`. Update `min_diff = diff` and `result = v`.
  - Because we are iterating `v` in increasing order, the first time we find a `value` that gives the minimum possible difference, it will be the smallest such `value`, automatically handling the tie-breaking rule.
- After checking all candidates, return `result`.

## Binary Search on the Answer
A key observation is that the sum of the mutated array is a monotonic function of the threshold `value`. As `value` increases, the sum of the mutated array also increases or stays the same. This property allows us to use binary search to efficiently find the optimal `value` instead of checking every single possibility.
**Time:** O(N * log M) - The binary search performs `log M` iterations, where M is the search range for `value`. In each iteration, we compute the sum, which takes O(N) time. · **Space:** O(1) - Constant extra space is used.
**Pros:** Significantly more efficient than the brute-force approach.; Guaranteed to find the optimal solution within logarithmic time relative to the search range.
**Cons:** While much faster than brute force, it might not be the most optimal solution, as each step of the binary search still requires a full O(N) scan of the array.
### Explanation
Instead of a linear scan, we can significantly speed up the search for the optimal `value` by using binary search. The search space for `value` is still the range of integers from 0 to an upper bound like 100001.

Let's define a function `getSum(v)` that computes the sum of the array when all elements larger than `v` are replaced by `v`. This function is monotonic: if `v1 < v2`, then `getSum(v1) <= getSum(v2)`. This allows us to apply binary search.

We binary search for `value` in the range `[0, 100001]`. In each step, we take the middle element `mid` as a candidate `value`, compute `getSum(mid)`, and compare it to `target`.
- If `getSum(mid)` is less than `target`, we know that `mid` and all values smaller than it will result in a sum that is even further from `target` on the lower side. So, we need to explore larger values by setting `low = mid + 1`.
- If `getSum(mid)` is greater than or equal to `target`, `mid` could be a potential answer, but a smaller `value` might give a sum that is also close to `target`. We explore smaller values by setting `high = mid - 1`.

This binary search will not necessarily land on the exact best value, but it will narrow the possibilities down to two candidates. When the loop terminates (`low > high`), the best `value` is guaranteed to be either `low` or `high`. We can then compute `getSum(low)` and `getSum(high)`, compare their absolute differences to `target`, and choose the one that results in a smaller difference. In case of a tie, we choose the smaller value, which will be `high`.

```java
class Solution {
    public int findBestValue(int[] arr, int target) {
        int low = 0;
        // A safe upper bound from constraints
        int high = 100001;
        int ans = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            long sum = getSum(arr, mid);
            if (sum < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        // After the loop, low and high are the best candidates.
        // Let's check which one is closer to the target.
        long sumLow = getSum(arr, high);
        long sumHigh = getSum(arr, low);

        if (Math.abs(sumLow - target) <= Math.abs(sumHigh - target)) {
            return high;
        } else {
            return low;
        }
    }

    private long getSum(int[] arr, int value) {
        long sum = 0;
        for (int num : arr) {
            sum += Math.min(num, value);
        }
        return sum;
    }
}
```
### Algorithm
- Define a helper function `getSum(v, arr)` that takes a value `v` and the array `arr`, and returns the sum of the mutated array. This function iterates through `arr` and sums up `min(num, v)` for each `num`.
- The function `getSum(v, arr)` is monotonically non-decreasing with respect to `v`.
- We can use binary search on the possible answer `value`. The search space for `value` is from 0 to a safe upper bound like 100001.
- Initialize `low = 0`, `high = 100001`.
- While `low <= high`:
  - Calculate `mid = low + (high - low) / 2`.
  - Compute `current_sum = getSum(mid, arr)`.
  - If `current_sum < target`, it means `mid` is too small to reach the target, so we need to try larger values. We set `low = mid + 1`.
  - If `current_sum >= target`, `mid` might be the answer or it might be too large. We try smaller values by setting `high = mid - 1`.
- The loop terminates when `low > high`. The optimal integer value must be one of `high` or `low` (the two values surrounding the point where the sum crosses the target).
- Calculate the sum for `high` and `low`, find their absolute differences from `target`, and return the value that gives the smaller difference. If the differences are equal, return the smaller value (`high`).

## Sorting with Analytical Solution
This approach optimizes the process by first sorting the array. After sorting, we can iterate through the array and, at each step, analytically determine the best possible `value` for the remaining part of the array. This avoids the need for a nested loop or a binary search on the answer, leading to a more efficient solution.
**Time:** O(N log N) - Dominated by the initial sorting of the array. The subsequent loop runs in O(N) time. · **Space:** O(log N) or O(N) - This depends on the space complexity of the sorting algorithm used. In Java, `Arrays.sort` for primitives uses a dual-pivot quicksort which takes O(log N) space on average.
**Pros:** This is the most efficient approach for the given constraints.; It solves the problem with a single pass after sorting.
**Cons:** Requires sorting the array, which takes O(N log N) time and might require extra space.; The logic is more involved than the binary search approach.
### Explanation
By sorting the array `arr`, we can process elements in a structured way. The core idea is that for any chosen `value`, all elements in `arr` smaller than `value` will contribute their original value to the sum, while all elements larger than `value` will contribute `value` to the sum.

Let's iterate through the sorted array and maintain a `prefix_sum` of the elements we've passed. At index `i`, `prefix_sum` holds the sum of `arr[0]` through `arr[i-1]`. The remaining `n-i` elements are `arr[i], ..., arr[n-1]`. If we were to choose a `value` such that `arr[i-1] < value <= arr[i]`, the total sum would be `prefix_sum + (n-i) * value`.

We want this sum to be as close as possible to `target`. We can find an ideal (potentially fractional) `value` by solving `prefix_sum + (n-i) * value = target`, which gives `value = (target - prefix_sum) / (n-i)`.

Our algorithm iterates through the sorted array. At each index `i`, we check if the `target` can be achieved by a `value <= arr[i]`. This is true if `target <= prefix_sum + (n-i) * arr[i]`. Once this condition is met, we've located the segment where the optimal `value` lies. We then calculate the ideal `value` as described above. Since the answer must be an integer, the best candidates are the two integers surrounding the ideal fractional value. We check these two integers, see which one produces a sum closer to `target`, and return it, respecting the tie-breaking rule.

If the loop completes, it means the `target` is larger than the sum of the original array. The best we can do is not mutate the array at all. The minimum `value` to achieve this is the largest element in the array, `arr[n-1]`.

```java
import java.util.Arrays;

class Solution {
    public int findBestValue(int[] arr, int target) {
        Arrays.sort(arr);
        int n = arr.length;
        long prefixSum = 0;

        for (int i = 0; i < n; i++) {
            long remainingCount = n - i;
            // Check if the target is achievable with a value <= arr[i]
            if (prefixSum + remainingCount * arr[i] >= target) {
                // The ideal value is in the range (arr[i-1], arr[i]]
                // (or [0, arr[0]] for i=0)
                long valueLow = (target - prefixSum) / remainingCount;
                long valueHigh = valueLow + 1;

                long sumLow = prefixSum + remainingCount * valueLow;
                long sumHigh = prefixSum + remainingCount * valueHigh;

                if (Math.abs(target - sumLow) <= Math.abs(target - sumHigh)) {
                    return (int) valueLow;
                } else {
                    return (int) valueHigh;
                }
            }
            prefixSum += arr[i];
        }

        // If target is greater than the total sum of the array
        return arr[n - 1];
    }
}
```
### Algorithm
- First, sort the input array `arr` in non-decreasing order.
- Initialize a `prefix_sum` to 0. This will store the sum of elements we have processed so far.
- Iterate through the sorted array from `i = 0` to `n-1`.
  - At each index `i`, calculate the number of remaining elements: `remaining_count = n - i`.
  - Consider the sum if we were to cap all remaining elements at the current value `arr[i]`. This sum would be `prefix_sum + remaining_count * arr[i]`.
  - If this potential sum is greater than or equal to `target`, it means the ideal `value` is less than or equal to `arr[i]` and greater than `arr[i-1]`. We have found the correct segment to search for the answer.
  - The ideal (possibly fractional) value that would make the sum exactly `target` is `(target - prefix_sum) / remaining_count`.
  - We need to find the best integer value. The best integer is the one closest to this ideal fractional value. We can find this by checking the integers `v_low = (target - prefix_sum) / remaining_count` (integer division) and `v_high = v_low + 1`.
  - Calculate the sums for `v_low` and `v_high` and return the one that gives a sum closer to `target`. If differences are equal, `v_low` is chosen as it's smaller.
  - Once the best value is found and returned, the algorithm terminates.
- If the loop finishes without returning, it means `target` is larger than the sum of the original array. The closest we can get is the original sum, which is achieved by any `value >= arr[n-1]`. The minimum such value is `arr[n-1]`, so we return it.

# Solutions
### Java

```java
class Solution {
public
  int findBestValue(int[] arr, int target) {
    Arrays.sort(arr);
    int n = arr.length;
    int[] s = new int[n + 1];
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + arr[i];
      mx = Math.max(mx, arr[i]);
    }
    int ans = 0, diff = 1 << 30;
    for (int value = 0; value <= mx; ++value) {
      int i = search(arr, value);
      int d = Math.abs(s[i] + (n - i) * value - target);
      if (diff > d) {
        diff = d;
        ans = value;
      }
    }
    return ans;
  }
private
  int search(int[] arr, int x) {
    int left = 0, right = arr.length;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (arr[mid] > x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findBestValue(vector<int> &arr, int target) {
    sort(arr.begin(), arr.end());
    int n = arr.size();
    int s[n + 1];
    s[0] = 0;
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + arr[i];
      mx = max(mx, arr[i]);
    }
    int ans = 0, diff = 1 << 30;
    for (int value = 0; value <= mx; ++value) {
      int i = upper_bound(arr.begin(), arr.end(), value) - arr.begin();
      int d = abs(s[i] + (n - i) * value - target);
      if (diff > d) {
        diff = d;
        ans = value;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int: arr . sort() s = list(accumulate(arr, initial=0)) ans, diff = 0, inf for value in range(max(arr) + 1): i = bisect_right(arr, value) d = abs(s[i] + (len(arr) - i) * value - target) if diff > d: diff = d ans = value return ans

```