Minimize Rounding Error to Meet Target
Minimize Rounding Error to Meet Target is a medium arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (greedy on the largest fractional parts), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from dynamic programming over the number of round-ups up.
Problem
You are given a list of prices as strings, each with exactly three digits after the decimal point, and an integer target. Every price p must be rounded to a whole number, either down to floor(p) or up to ceil(p), so that the rounded values add up to exactly target.
The rounding error of one price is |rounded - p|, and the total error is the sum over all prices. Return the smallest possible total error as a string with exactly three decimal places, such as "0.900". If no choice of roundings reaches target, return "-1".
Examples
Example 1
- Input
prices = ["1.200", "2.500", "3.800"], target = 8- Output
"0.900"- Why
- Round 1.200 down, 2.500 up and 3.800 up: 1 + 3 + 4 = 8, with error 0.2 + 0.5 + 0.2 = 0.9.
Example 2
- Input
prices = ["0.500", "0.500"], target = 3- Output
"-1"- Why
- Even rounding both prices up only reaches 2.
Example 3
- Input
prices = ["4.000", "1.250"], target = 5- Output
"0.250"- Why
- 4.000 is already whole, so it adds 4 either way and no error; 1.250 must be rounded down.
Constraints
1 <= prices.length <= 500- Each
prices[i]is a number from0.000to1000.000written with exactly three digits after the decimal point. 0 <= target <= 10^6
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Dynamic programming over the number of round-ups | O(n²) | O(n) |
| Optimal (greedy on the largest fractional parts) | O(n log n) | O(n) |
1Dynamic programming over the number of round-ups
O(n²)Each of the m ≤ n fractional prices updates up to m + 1 DP cells.O(n)One array of m + 1 error totals.Convert each price to an integer number of thousandths. Whole prices are fixed. For the fractional ones, compute dp[j] = the smallest total error (in thousandths) when exactly j of the prices seen so far are rounded up. After all prices, dp[k] is the answer when k = target - sum(floors) is in range.
- Parse each price as
vthousandths; addv / 1000tolowand collectf = v % 1000when it is not zero. - Let
mbe the number of collected fractions andk = target - low; ifk < 0ork > m, return "-1". - Set
dp[0] = 0and the rest to infinity. For each fractionf, update j from high to low:dp[j] = min(dp[j] + f, dp[j - 1] + 1000 - f), anddp[0] += f. - Format
dp[k]aswhole.fffwith three decimals.
class Solution {
public String minimizeError(String[] prices, int target) {
long low = 0;
List<Integer> fracs = new ArrayList<>();
for (String p : prices) {
long v = Long.parseLong(p.replace(".", ""));
low += v / 1000;
if (v % 1000 != 0) fracs.add((int) (v % 1000));
}
int m = fracs.size();
long k = target - low;
if (k < 0 || k > m) return "-1";
long INF = Long.MAX_VALUE / 4;
long[] dp = new long[m + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int f : fracs) {
for (int j = m; j >= 1; j--) dp[j] = Math.min(dp[j] + f, dp[j - 1] + 1000 - f);
dp[0] += f;
}
long err = dp[(int) k];
return String.format("%d.%03d", err / 1000, err % 1000);
}
}class Solution:
def minimizeError(self, prices: List[str], target: int) -> str:
low = 0
fracs = []
for p in prices:
v = int(p.replace(".", ""))
low += v // 1000
if v % 1000:
fracs.append(v % 1000)
m = len(fracs)
k = target - low
if k < 0 or k > m:
return "-1"
INF = float("inf")
dp = [0] + [INF] * m
for f in fracs:
for j in range(m, 0, -1):
dp[j] = min(dp[j] + f, dp[j - 1] + 1000 - f)
dp[0] += f
err = dp[k]
return f"{err // 1000}.{err % 1000:03d}"class Solution {
public:
string minimizeError(vector<string>& prices, int target) {
long long low = 0;
vector<int> fracs;
for (auto& p : prices) {
string digits;
for (char c : p)
if (c != '.') digits += c;
long long v = stoll(digits);
low += v / 1000;
if (v % 1000 != 0) fracs.push_back(v % 1000);
}
int m = fracs.size();
long long k = target - low;
if (k < 0 || k > m) return "-1";
const long long INF = LLONG_MAX / 4;
vector<long long> dp(m + 1, INF);
dp[0] = 0;
for (int f : fracs) {
for (int j = m; j >= 1; j--) dp[j] = min(dp[j] + f, dp[j - 1] + 1000 - f);
dp[0] += f;
}
long long err = dp[k];
string frac = to_string(err % 1000);
while (frac.size() < 3) frac = "0" + frac;
return to_string(err / 1000) + "." + frac;
}
};function minimizeError(prices, target) {
let low = 0;
const fracs = [];
for (const p of prices) {
const v = Number(p.replace(".", ""));
low += Math.floor(v / 1000);
if (v % 1000 !== 0) fracs.push(v % 1000);
}
const m = fracs.length;
const k = target - low;
if (k < 0 || k > m) return "-1";
const dp = new Array(m + 1).fill(Infinity);
dp[0] = 0;
for (const f of fracs) {
for (let j = m; j >= 1; j--) dp[j] = Math.min(dp[j] + f, dp[j - 1] + 1000 - f);
dp[0] += f;
}
const err = dp[k];
return Math.floor(err / 1000) + "." + String(err % 1000).padStart(3, "0");
}2Optimal (greedy on the largest fractional parts)
O(n log n)Sorting the fractional parts dominates; everything else is one pass.O(n)The list of fractional parts.Start from rounding every price down, which costs the sum of all fractional parts. Switching one fractional price from down to up changes the cost from f to 1000 - f (in thousandths). Exactly k switches are required, so choose the k prices with the largest fractional parts, where the switch costs the least.
- Parse prices into thousandths; sum the floors into
lowand collect the nonzero fractions. - Compute
k = target - low; return "-1" ifk < 0orkexceeds the number of fractions. - Sort the fractions in descending order. The first k cost
1000 - feach, the rest costfeach. - Format the total as
whole.fff.
class Solution {
public String minimizeError(String[] prices, int target) {
long low = 0;
List<Integer> fracs = new ArrayList<>();
for (String p : prices) {
long v = Long.parseLong(p.replace(".", ""));
low += v / 1000;
if (v % 1000 != 0) fracs.add((int) (v % 1000));
}
long k = target - low;
if (k < 0 || k > fracs.size()) return "-1";
fracs.sort(Collections.reverseOrder());
long err = 0;
for (int i = 0; i < fracs.size(); i++) err += i < k ? 1000 - fracs.get(i) : fracs.get(i);
return String.format("%d.%03d", err / 1000, err % 1000);
}
}class Solution:
def minimizeError(self, prices: List[str], target: int) -> str:
low = 0
fracs = []
for p in prices:
v = int(p.replace(".", ""))
low += v // 1000
if v % 1000:
fracs.append(v % 1000)
k = target - low
if k < 0 or k > len(fracs):
return "-1"
fracs.sort(reverse=True)
err = 0
for i, f in enumerate(fracs):
err += 1000 - f if i < k else f
return f"{err // 1000}.{err % 1000:03d}"class Solution {
public:
string minimizeError(vector<string>& prices, int target) {
long long low = 0;
vector<int> fracs;
for (auto& p : prices) {
string digits;
for (char c : p)
if (c != '.') digits += c;
long long v = stoll(digits);
low += v / 1000;
if (v % 1000 != 0) fracs.push_back(v % 1000);
}
long long k = target - low;
if (k < 0 || k > (long long)fracs.size()) return "-1";
sort(fracs.rbegin(), fracs.rend());
long long err = 0;
for (int i = 0; i < (int)fracs.size(); i++) err += i < k ? 1000 - fracs[i] : fracs[i];
string frac = to_string(err % 1000);
while (frac.size() < 3) frac = "0" + frac;
return to_string(err / 1000) + "." + frac;
}
};function minimizeError(prices, target) {
let low = 0;
const fracs = [];
for (const p of prices) {
const v = Number(p.replace(".", ""));
low += Math.floor(v / 1000);
if (v % 1000 !== 0) fracs.push(v % 1000);
}
const k = target - low;
if (k < 0 || k > fracs.length) return "-1";
fracs.sort((a, b) => b - a);
let err = 0;
for (let i = 0; i < fracs.length; i++) err += i < k ? 1000 - fracs[i] : fracs[i];
return Math.floor(err / 1000) + "." + String(err % 1000).padStart(3, "0");
}Edge cases to test
- Whole-number prices, which can only contribute their own value
- Target below the sum of all floors or above the sum of all ceilings
- Target equal to the sum of floors (round everything down) or of ceilings
- Several prices with the same fractional part
Hints
Hint 1
Rounding a price down costs its fractional part f; rounding it up costs 1 - f. Whole prices cost nothing and cannot change the sum.
Hint 2
Start from all floors. To hit the target you must round up exactly k = target - sum(floors) of the prices that have a fractional part; if k is negative or too big, the answer is -1.
Hint 3
Rounding a price up instead of down changes the error by 1 - 2f, so the k best prices to round up are the ones with the largest fractional parts. Work in thousandths to avoid floating-point trouble.
FAQ
What is the best time complexity for Minimize Rounding Error to Meet Target?
Optimal (greedy on the largest fractional parts) runs in O(n log n) time and O(n) extra space. Sorting the fractional parts dominates; everything else is one pass.
Which pattern does Minimize Rounding Error to Meet Target use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.
Is there a brute force solution for Minimize Rounding Error to Meet Target?
Yes. Dynamic programming over the number of round-ups takes O(n²) time and O(n) space. Convert each price to an integer number of thousandths.
Which edge cases should I test for Minimize Rounding Error to Meet Target?
Whole-number prices, which can only contribute their own value; Target below the sum of all floors or above the sum of all ceilings; Target equal to the sum of floors (round everything down) or of ceilings; Several prices with the same fractional part.