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
PythonJavaC++Go
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}'(code-box)
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);
}
}(code-box)
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);
}
};(code-box)
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)
}(code-box)
