Problem

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.

Examples

Example 1

1
2
3
4
5

Input: prices = ["0.700","2.800","4.900"], target = 8
Output: "1.000"
Explanation:
Use floor for 0.700 and ceil for 2.800 and 4.900.
The rounded prices are [0,3,5], and the rounding error is |0.700-0| + |2.800-3| + |4.900-5| = 0.700 + 0.200 + 0.100 = 1.000

Example 2

1
2
3
4

Input: prices = ["1.500","2.500","3.500"], target = 10
Output: "-1"
Explanation:
It is impossible to meet the target.

Constraints

  • 1 <= prices.length <= 10^5
  • 0 <= float(prices[i]) <= 1000
  • 0 <= target <= 10^6

Solution

Method 1 – Greedy + Sorting

Intuition

For each price, you can round down (floor) or up (ceil). To minimize the rounding error, round down as much as possible, and only round up for the minimum number of prices needed to reach the target. The prices with the smallest difference between ceil and the original value should be chosen for rounding up.

Approach

  1. For each price, compute its floor and ceil, and the difference between the price and its floor (error if floored).
  2. Calculate the sum if all prices are floored and the sum if all are ceiled.
  3. If the target is not between these two sums, return “-1”.
  4. The number of prices to round up is target - floor_sum.
  5. Sort the prices by their fractional part (error if floored), and pick the smallest errors to round up.
  6. Sum the rounding errors accordingly and format the result to three decimal places.

Code

 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

class Solution {
public:
    string minimizeError(vector<string>& prices, int target) {
        vector<double> errors;
        int floor_sum = 0, ceil_sum = 0;
        for (auto& p : prices) {
            double v = stod(p);
            int f = floor(v), c = ceil(v);
            floor_sum += f;
            ceil_sum += c;
            if (f != c) errors.push_back(v - f);
        }
        int up = target - floor_sum;
        if (up < 0 || up > errors.size()) return "-1";
        sort(errors.begin(), errors.end());
        double ans = 0;
        for (int i = 0; i < errors.size(); ++i) {
            if (i < up) ans += 1 - errors[i];
            else ans += errors[i];
        }
        char buf[16];
        sprintf(buf, "%.3f", ans);
        return string(buf);
    }
};
 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

func minimizeError(prices []string, target int) string {
    errors := []float64{}
    floorSum, ceilSum := 0, 0
    for _, p := range prices {
        v, _ := strconv.ParseFloat(p, 64)
        f := int(math.Floor(v))
        c := int(math.Ceil(v))
        floorSum += f
        ceilSum += c
        if f != c {
            errors = append(errors, v-f)
        }
    }
    up := target - floorSum
    if up < 0 || up > len(errors) {
        return "-1"
    }
    sort.Float64s(errors)
    ans := 0.0
    for i, e := range errors {
        if i < up {
            ans += 1 - e
        } else {
            ans += e
        }
    }
    return fmt.Sprintf("%.3f", ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public String minimizeError(List<String> prices, int target) {
        List<Double> errors = new ArrayList<>();
        int floorSum = 0, ceilSum = 0;
        for (String p : prices) {
            double v = Double.parseDouble(p);
            int f = (int)Math.floor(v), c = (int)Math.ceil(v);
            floorSum += f;
            ceilSum += c;
            if (f != c) errors.add(v - f);
        }
        int up = target - floorSum;
        if (up < 0 || up > errors.size()) return "-1";
        Collections.sort(errors);
        double ans = 0;
        for (int i = 0; i < errors.size(); ++i) {
            if (i < up) ans += 1 - errors.get(i);
            else ans += errors.get(i);
        }
        return String.format("%.3f", ans);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun minimizeError(prices: List<String>, target: Int): String {
        val errors = mutableListOf<Double>()
        var floorSum = 0
        var ceilSum = 0
        for (p in prices) {
            val v = p.toDouble()
            val f = v.toInt()
            val c = Math.ceil(v).toInt()
            floorSum += f
            ceilSum += c
            if (f != c) errors.add(v - f)
        }
        val up = target - floorSum
        if (up < 0 || up > errors.size) return "-1"
        errors.sort()
        var ans = 0.0
        for (i in errors.indices) {
            ans += if (i < up) 1 - errors[i] else errors[i]
        }
        return "%.3f".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

def minimize_error(prices: list[str], target: int) -> str:
    errors: list[float] = []
    floor_sum = 0
    ceil_sum = 0
    for p in prices:
        v = float(p)
        f = int(v)
        c = int(-(-v // 1))
        floor_sum += f
        ceil_sum += c
        if f != c:
            errors.append(v - f)
    up = target - floor_sum
    if up < 0 or up > len(errors):
        return "-1"
    errors.sort()
    ans = 0.0
    for i, e in enumerate(errors):
        if i < up:
            ans += 1 - e
        else:
            ans += e
    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
29
30
31

impl Solution {
    pub fn minimize_error(prices: Vec<String>, target: i32) -> String {
        let mut errors = vec![];
        let mut floor_sum = 0;
        let mut ceil_sum = 0;
        for p in prices.iter() {
            let v: f64 = p.parse().unwrap();
            let f = v.floor() as i32;
            let c = v.ceil() as i32;
            floor_sum += f;
            ceil_sum += c;
            if f != c {
                errors.push(v - f as f64);
            }
        }
        let up = target - floor_sum;
        if up < 0 || up as usize > errors.len() {
            return "-1".to_string();
        }
        errors.sort_by(|a, b| a.partial_cmp(b).unwrap());
        let mut ans = 0.0;
        for (i, e) in errors.iter().enumerate() {
            if i < up as usize {
                ans += 1.0 - e;
            } else {
                ans += *e;
            }
        }
        format!("{:.3}", ans)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    minimizeError(prices: string[], target: number): string {
        let errors: number[] = [];
        let floorSum = 0, ceilSum = 0;
        for (const p of prices) {
            const v = parseFloat(p);
            const f = Math.floor(v), c = Math.ceil(v);
            floorSum += f;
            ceilSum += c;
            if (f !== c) errors.push(v - f);
        }
        const up = target - floorSum;
        if (up < 0 || up > errors.length) return "-1";
        errors.sort((a, b) => a - b);
        let ans = 0;
        for (let i = 0; i < errors.length; ++i) {
            if (i < up) ans += 1 - errors[i];
            else ans += errors[i];
        }
        return ans.toFixed(3);
    }
}

Complexity

  • ⏰ Time complexity: O(n log n)
    • Sorting the errors array dominates.
  • 🧺 Space complexity: O(n)
    • For storing the errors array.