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 i1 to n
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 <= 500prices[i] represents a real number in the range [0.0, 1000.0] and has exactly 3 decimal places.0 <= target <= 106Problem Overview: You receive prices as decimal strings. Each value can be rounded either down (floor) or up (ceil). The goal is to choose rounding directions so the total equals a given integer target while minimizing the total rounding error.
Approach 1: Greedy with Sorting (O(n log n) time, O(n) space)
Start by converting each string to a number and computing its floor and ceil. If a value is already an integer, both operations give the same result and must be used as-is. Compute floorSum and ceilSum across the array. If the target is outside this range, no combination of rounding operations can reach it.
The key decision is how many numbers must be rounded up. That value is k = target - floorSum. Initially assume every non-integer is rounded down, which produces error equal to its fractional part. Rounding up changes the error to 1 - fraction. The extra cost of switching from down to up is (1 - fraction) - fraction. Sort numbers by this extra cost and choose the k smallest values to round up. This greedy choice minimizes total error because the numbers closest to the next integer have the cheapest upward rounding cost. The algorithm relies on simple arithmetic and sorting from math and sorting.
Approach 2: Greedy with Heap (O(n log n) time, O(n) space)
Instead of sorting the entire list, push the cost difference for each non-integer price into a min-heap. After computing k = target - floorSum, pop the smallest k costs and treat those numbers as rounded up. The rest remain rounded down. This produces the same result as sorting but can be easier to implement if you prefer incremental selection logic.
Both strategies rely on the same greedy observation: rounding up numbers with the largest fractional parts produces the smallest additional error. The heap version emphasizes selection, while the sorting version keeps the logic simpler.
Recommended for interviews: The greedy sorting approach is the expected solution. It demonstrates understanding of rounding boundaries, feasibility checks, and cost-based greedy decisions. Interviewers often want to see the reasoning behind computing k = target - floorSum and why sorting fractional costs guarantees minimal total error. This pattern frequently appears in greedy optimization problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(n) | General case. Simple implementation and the most common interview solution. |
| Greedy with Min Heap | O(n log n) | O(n) | Useful when selecting the k smallest rounding costs without sorting the entire array. |
猩猩的乐园 LeetCode 1058 Minimize Rounding Error to Meet Target • 猩猩的乐园 • 599 views views
Watch 2 more video solutions →Practice Minimize Rounding Error to Meet Target with our built-in code editor and test cases.
Practice on FleetCode