Minimize Rounding Error to Meet Target
Problem
Given an array of decimal price strings prices and an integer target, round each price either down (floor) or up (ceil) so that the sum of the rounded prices equals target. Minimize the total rounding error — the sum of |round(price) − price| — and return it as a string with exactly three decimals. If it is impossible to reach target, return "-1".
prices = ["2.700", "3.400", "5.900"], target = 11"1.200"import math
def minimize_error(prices, target):
floor_sum = 0
fracs = []
for p in prices:
v = float(p)
floor_sum += math.floor(v)
fracs.append(v - math.floor(v))
up = target - floor_sum
n = len(prices)
if up < 0 or up > n:
return "-1"
fracs.sort(reverse=True)
err = 0.0
for i, f in enumerate(fracs):
if i < up:
err += 1 - f # this price is rounded up
else:
err += f # this price is rounded down
return "%.3f" % errfunction minimizeError(prices, target) {
let floorSum = 0;
const fracs = [];
for (const p of prices) {
const v = parseFloat(p);
floorSum += Math.floor(v);
fracs.push(v - Math.floor(v));
}
const up = target - floorSum;
const n = prices.length;
if (up < 0 || up > n) return "-1";
fracs.sort((a, b) => b - a);
let err = 0;
for (let i = 0; i < n; i++) {
if (i < up) err += 1 - fracs[i]; // rounded up
else err += fracs[i]; // rounded down
}
return err.toFixed(3);
}class Solution {
public String minimizeError(String[] prices, int target) {
int floorSum = 0;
double[] fracs = new double[prices.length];
for (int i = 0; i < prices.length; i++) {
double v = Double.parseDouble(prices[i]);
floorSum += (int) Math.floor(v);
fracs[i] = v - Math.floor(v);
}
int up = target - floorSum, n = prices.length;
if (up < 0 || up > n) return "-1";
Arrays.sort(fracs); // ascending
double err = 0;
for (int i = 0; i < n; i++) {
// largest 'up' fracs (at the end) are rounded up
if (i >= n - up) err += 1 - fracs[i];
else err += fracs[i];
}
return String.format("%.3f", err);
}
}string minimizeError(vector<string>& prices, int target) {
int floorSum = 0, n = prices.size();
vector<double> fracs;
for (auto& p : prices) {
double v = stod(p);
floorSum += (int)floor(v);
fracs.push_back(v - floor(v));
}
int up = target - floorSum;
if (up < 0 || up > n) return "-1";
sort(fracs.rbegin(), fracs.rend()); // descending
double err = 0;
for (int i = 0; i < n; i++) {
if (i < up) err += 1 - fracs[i]; // rounded up
else err += fracs[i]; // rounded down
}
char buf[32];
snprintf(buf, sizeof(buf), "%.3f", err);
return string(buf);
}Explanation
Each price must be rounded either down or up. If we start by flooring every price, we get a baseline sum. To hit target, we then need to round exactly up = target - floorSum of the prices up instead (each upward round adds 1 to the sum). If up is negative or bigger than the number of prices, the target is impossible and we return "-1".
The question becomes: which prices should we round up to keep the total error smallest? Rounding a price down costs its fractional part f; rounding it up costs 1 - f. A price with a big fraction (close to the next integer) is cheap to round up and expensive to round down.
So we sort the fractional parts from largest to smallest and round up the first up of them (the ones with big fractions, cheapest to push up). Everything else is rounded down. This greedy split minimizes the total error.
We add 1 - f for each rounded-up price and f for each rounded-down price, then format the answer to three decimals.
Example: prices = ["2.700", "3.400", "5.900"], target = 11. Floor sum is 2+3+5 = 10, so up = 1. The biggest fraction is 0.9 (from 5.9), so round it up (cost 0.1) and floor the rest (costs 0.7 and 0.4). Total error is 1.200.