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

Posted Jun 15, 20203 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.

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;