Greedy
Array
Math
String
Sorting
Description
Given an array of prices
[p1 ,p2 ...,pn ]
and a target
, round each price pi
to Roundi (pi )
so that the rounded array [Round1 (p1 ),Round2 (p2 )...,Roundn (pn )]
sums to the given target
. Each operation Roundi (pi )
could be either Floor(pi )
or Ceil(pi )
.
Return the string "-1"
if the rounded array is impossible to sum to target
. Otherwise, return the smallest rounding error, which is defined as Σ |Roundi (pi ) - (pi )|
for i
from 1
to n
, as a string with three places after the decimal.
Example 1:
Input: prices = ["0.700","2.800","4.900"], target = 8
Output: "1.000"
Explanation:
Use Floor, Ceil and Ceil operations to get (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = 0.7 + 0.2 + 0.1 = 1.0 .
Example 2:
Input: prices = ["1.500","2.500","3.500"], target = 10
Output: "-1"
Explanation: It is impossible to meet the target.
Example 3:
Input: prices = ["1.500","2.500","3.500"], target = 9
Output: "1.500"
Constraints:
1 <= prices.length <= 500
Each string prices[i]
represents a real number in the range [0.0, 1000.0]
and has exactly 3 decimal places.
0 <= target <= 106
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution :
def minimizeError ( self , prices : List [ str ], target : int ) -> str :
mi = 0
arr = []
for p in prices :
p = float ( p )
mi += int ( p )
if d := p - int ( p ):
arr . append ( d )
if not mi <= target <= mi + len ( arr ):
return "-1"
d = target - mi
arr . sort ( reverse = True )
ans = d - sum ( arr [: d ]) + sum ( arr [ d :])
return f ' { ans : .3f } '
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 class Solution {
public String minimizeError ( String [] prices , int target ) {
int mi = 0 ;
List < Double > arr = new ArrayList <> ();
for ( String p : prices ) {
double price = Double . valueOf ( p );
mi += ( int ) price ;
double d = price - ( int ) price ;
if ( d > 0 ) {
arr . add ( d );
}
}
if ( target < mi || target > mi + arr . size ()) {
return "-1" ;
}
int d = target - mi ;
arr . sort ( Collections . reverseOrder ());
double ans = d ;
for ( int i = 0 ; i < d ; ++ i ) {
ans -= arr . get ( i );
}
for ( int i = d ; i < arr . size (); ++ i ) {
ans += arr . get ( i );
}
DecimalFormat df = new DecimalFormat ( "#0.000" );
return df . format ( 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 class Solution {
public :
string minimizeError ( vector < string >& prices , int target ) {
int mi = 0 ;
vector < double > arr ;
for ( auto & p : prices ) {
double price = stod ( p );
mi += ( int ) price ;
double d = price - ( int ) price ;
if ( d > 0 ) {
arr . push_back ( d );
}
}
if ( target < mi || target > mi + arr . size ()) {
return "-1" ;
}
int d = target - mi ;
sort ( arr . rbegin (), arr . rend ());
double ans = d ;
for ( int i = 0 ; i < d ; ++ i ) {
ans -= arr [ i ];
}
for ( int i = d ; i < arr . size (); ++ i ) {
ans += arr [ i ];
}
string s = to_string ( ans );
return s . substr ( 0 , s . find ( '.' ) + 4 );
}
};
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 func minimizeError ( prices [] string , target int ) string {
arr := [] float64 {}
mi := 0
for _ , p := range prices {
price , _ := strconv . ParseFloat ( p , 64 )
mi += int ( math . Floor ( price ))
d := price - float64 ( math . Floor ( price ))
if d > 0 {
arr = append ( arr , d )
}
}
if target < mi || target > mi + len ( arr ) {
return "-1"
}
d := target - mi
sort . Float64s ( arr )
ans := float64 ( d )
for i := 0 ; i < d ; i ++ {
ans -= arr [ len ( arr ) - i - 1 ]
}
for i := d ; i < len ( arr ); i ++ {
ans += arr [ len ( arr ) - i - 1 ]
}
return fmt . Sprintf ( "%.3f" , ans )
}
GitHub