MediumNo. 1058LeetCode Premium
Minimize Rounding Error to Meet Target — LeetCode 1058 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array, Math, String, Sorting
- Reading time
- 3 min
- Source
- leetcode.com
The 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).
Example
- 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 .
Python solution
class Solution:
def minimizeError(self, prices: List[str], target: int) -> str:
mi = 0
arr = []
for p in prices:
p = float(p)
mi += int(p)
if d := p - int(p):
arr.append(d)
if not mi <= target <= mi + len(arr):
return "-1"
d = target - mi
arr.sort(reverse=True)
ans = d - sum(arr[:d]) + sum(arr[d:])
return f'{ans:.3f}'Complexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1058. Minimize Rounding Error to Meet Target is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0179 | Largest Number | Medium |
| 0910 | Smallest Range II | Medium |
| 0976 | Largest Perimeter Triangle | Easy |
| 1561 | Maximum Number of Coins You Can Get | Medium |
| 1686 | Stone Game VI | Medium |
| 2195 | Append K Integers With Minimal Sum | Medium |
Frequently asked questions
- How hard is LeetCode 1058. Minimize Rounding Error to Meet Target?
LeetCode 1058. Minimize Rounding Error to Meet Target is rated Medium on LeetCode.
- What topics does LeetCode 1058. Minimize Rounding Error to Meet Target cover?
LeetCode 1058. Minimize Rounding Error to Meet Target is tagged Greedy, Array, Math, String and Sorting on LeetCode.
- Is LeetCode 1058. Minimize Rounding Error to Meet Target a premium problem?
Yes. LeetCode 1058. Minimize Rounding Error to Meet Target is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.