Minimize Rounding Error to Meet Target

Medium Arrays & Hashing Greedy Original on LeetCode

Reported atAirbnb

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 from 0.000 to 1000.000 written 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.

00:00
Testcase

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.

ApproachTimeSpace
Dynamic programming over the number of round-upsO(n²)O(n)
Optimal (greedy on the largest fractional parts)O(n log n)O(n)

1Dynamic programming over the number of round-ups

TimeO(n²)Each of the m ≤ n fractional prices updates up to m + 1 DP cells.
SpaceO(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.

  1. Parse each price as v thousandths; add v / 1000 to low and collect f = v % 1000 when it is not zero.
  2. Let m be the number of collected fractions and k = target - low; if k < 0 or k > m, return "-1".
  3. Set dp[0] = 0 and the rest to infinity. For each fraction f, update j from high to low: dp[j] = min(dp[j] + f, dp[j - 1] + 1000 - f), and dp[0] += f.
  4. Format dp[k] as whole.fff with 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);
    }
}

2Optimal (greedy on the largest fractional parts)

TimeO(n log n)Sorting the fractional parts dominates; everything else is one pass.
SpaceO(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.

  1. Parse prices into thousandths; sum the floors into low and collect the nonzero fractions.
  2. Compute k = target - low; return "-1" if k < 0 or k exceeds the number of fractions.
  3. Sort the fractions in descending order. The first k cost 1000 - f each, the rest cost f each.
  4. 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);
    }
}

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.