Array
Binary Search
Sorting
Description
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
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 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 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 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 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 func findBestValue ( arr [] int , target int ) ( ans int ) {
sort . Ints ( arr )
n := len ( arr )
s := make ([] int , n + 1 )
mx := slices . Max ( arr )
for i , x := range arr {
s [ i + 1 ] = s [ i ] + x
}
diff := 1 << 30
for value := 0 ; value <= mx ; value ++ {
i := sort . SearchInts ( arr , value + 1 )
d := abs ( s [ i ] + ( n - i ) * value - target )
if diff > d {
diff = d
ans = value
}
}
return
}
func abs ( x int ) int {
if x < 0 {
return - x
}
return x
}
GitHub