# 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

| Item | Meaning |
|---|---|
| Input | Array of price strings and integer `target` |
| Output | Minimum rounding error as a string with two decimal places, or `"-1"` |

Function shape:

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

## Examples

Example 1:

```python
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:

```python
"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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting fractional parts |
| Space | `O(n)` | Store fractions |

## 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

```python
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

```python
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()
```

| Test | Expected | Why |
|---|---|---|
| Standard example | `"0.600"` | Optimal two ceilings |
| Impossible | `"-1"` | Sum `7`, target `10`, need `k=3`, max sum is `6` |