LeetCode 1058: Minimize Rounding Error to Meet Target

Problem Restatement

We are given an array of price strings (floating-point) and an integer target.

We must round each price either up (ceil) or down (floor).

We need the rounded prices to sum exactly to target.

Return the minimum total rounding error, or "-1" if it is impossible.

The official constraints state that 1 <= prices.length <= 500.

Input and Output

Function shape:

def minimizeError(prices: list[str], target: int) -> str:
    ...

Examples

Example 1:

prices = ["0.700","2.800","4.900"]
target = 8

Floor all: 0 + 2 + 4 = 6. Need to raise by 2. Raise the two with highest fractional parts: 2.800 → 3 (error 0.2), 4.900 → 5 (error 0.1).

Total error: 0.3 + 0.2 + 0.1 = 0.6.

Wait: floor all gives 0+2+4=6. Need sum 8, so 2 must be rounded up. Choose two with highest fractions: 0.9 and 0.8. Ceil them.

Total error: (1-0.7) + (0.2) + (0.1) = 0.3 + 0.2 + 0.1 = 0.6.

Answer:

"0.600"

Key Insight

Let floor_sum = sum(floor(p)) and fractions f_i = p_i - floor(p_i).

We need to ceil exactly target - floor_sum prices (call this k).

If k < 0 or k > n, return "-1".

Ceil the k prices with the largest fractional parts (they contribute the least additional error).

Total error = sum of k * (1 - f_i) for top k fractions + sum of (n-k) * f_i for remaining.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def minimizeError(self, prices: list[str], target: int) -> str:
        floors = [int(p.split('.')[0]) for p in prices]
        fractions = [float(p) - int(p.split('.')[0]) for p in prices]

        floor_sum = sum(floors)
        k = target - floor_sum

        if k < 0 or k > len(prices):
            return "-1"

        fractions.sort(reverse=True)
        error = sum(1 - f for f in fractions[:k]) + sum(fractions[k:])
        return f"{error:.3f}"[:-1]

Testing

def run_tests():
    s = Solution()

    assert s.minimizeError(["0.700","2.800","4.900"], 8) == "0.600"
    assert s.minimizeError(["1.500","2.500","3.500"], 10) == "-1"

    print("all tests passed")

run_tests()