# LeetCode 1300. The array closest to the target value after transforming the array and | Python

Posted Jun 15, 2020 • 3 min read

### 1300. The array and the closest to the target value after changing the array

Source:LeetCode [ https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target] ( https://leetcode-cn.com/problems/sum- of-mutated-array-closest-to-target)

#### Title

Give you an integer array arr and a target value, please return an integer value, so that after all values in the array greater than value become value, the sum of the array is closest to the target(the closest is the absolute value of the difference between the two) Minimum).

If there are multiple schemes that are closest to the target, please return the minimum of these integers.

Note that the answer is not necessarily the number in arr.

**Example 1:**

```
Input:arr = [4,9,3], target = 10
Output:3
Explanation:When the value is selected as 3, the array will become [3, 3, 3], and the sum is 9, which is the closest plan to the target.
```

**Example 2:**

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

**Example 3:**

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

**prompt:**

- 1 <= arr.length <= 10^4
- 1 <= arr[i], target <= 10^5

#### Problem solving ideas

**Thinking:binary search**

In this question, what may be more difficult is the question [value is an integer, array and close to target]and [the answer is not necessarily the number in arr]. In other words, the subject is the closest we want.

So the question now can be changed to consider how to judge proximity? The closest possible situation is listed below:

- Select a value and after the conversion, the sum of the array is equal to the target.(Of course, this is the ideal situation)
- The selected value is too large, the closeness becomes smaller;
- The selected value is too small, the closeness becomes larger.
- The second and third cases, the reverse may also be true.

How to consider the second and third cases, the solution adopted in this article is to determine the upper and lower boundaries, and compare the possible value values.

Specific practices:

- First determine a value, transform the array, and sum
- If the converted array sum is the first one greater than or equal to target, then determine the upper and lower boundaries
- Because value is an integer, the final answer may fall on value, or it may be value-1

The specific code implementation is as follows.

#### Code

```
class Solution:
def findBestValue(self, arr:List[int], target:int) -> int:
def cacl_change_sum(arr, value):
res = 0
# Values greater than value are to be converted
for num in arr:
res += min(num, value)
return res
left = 0
right = max(arr)
while left <right:
mid =(left+ right) //2
# Calculate the sum of the converted array
res = cacl_change_sum(arr, mid)
# Find the first value such that the transformed array is greater than or equal to target
if res <target:
left = mid + 1
else:
right = mid
# When the first value is found such that the converted array sum is greater than or equal to target, the answer may fall in value or value-1
# Now, compare the results between the two, the smaller the closeness, the return is the result
res1 = cacl_change_sum(arr, left)
res2 = cacl_change_sum(arr, left-1)
if res1-target <target-res2:
return left
return left-1
```

#### Results

#### to sum up

First clarify the meaning of the question, because there are requirements for [value is an integer, array and close to target]and [the answer is not necessarily a number in arr], so the question can start from considering how to find the closest solution;

The binary search used in this article, specific methods:

- Determine a value first, transform and sum the array
- If the sum of the array at this time is the first value greater than or equal to the target value, then the upper and lower boundaries can be determined at this time
- Since value must be an integer, the answer may fall on value or value-1.

The article is original, if you feel it is well written, welcome to follow and like it. The WeChat public account "Book Collection" is updated at the same time, and attention and likes are also welcome.