LeetCode 1058 - Minimize Rounding Error to Meet Target

Difficulty: 🟡 Medium
Topics: Array, Math, String, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to round an array of decimal prices to integers such that the sum of the rounded numbers equals a given target, while minimizing the total rounding error. Each price can be rounded either down (Floor) or up (Ceil). The rounding error for each price is defined as the absolute difference between the original price and its rounded value, and the total rounding error is the sum of these individual errors. If it is impossible to round the numbers to meet the target exactly, the function should return "-1".

The input consists of a list of strings, each representing a decimal number with exactly three decimal places, and an integer target. The output is a string representing the smallest possible rounding error, formatted to three decimal places.

The constraints tell us that the number of prices is relatively small (maximum 500), and the target can be quite large (up to 1,000,000). These constraints hint that a brute-force approach exploring all combinations of floors and ceils is infeasible, since the number of combinations grows exponentially.

Important edge cases include prices that are already integers, prices whose sum cannot match the target even if all are rounded up or down, and targets that are outside the possible sum range.

Approaches

The brute-force approach would involve generating all possible combinations of flooring or ceiling each price and checking if the sum matches the target. For each valid combination, we would compute the total rounding error and return the minimum. This approach is correct, but computationally infeasible, because it requires evaluating 2^n combinations for n prices, which is astronomically large for n = 500.

The key observation that enables an optimal solution is that each price can only contribute either its floor or its ceiling. If we sum all the floors and all the ceilings, the sum of floors gives the minimum possible sum, and the sum of ceilings gives the maximum possible sum. If the target is outside this range, it is impossible to meet the target, and we can immediately return "-1". Otherwise, we can sort the prices based on their fractional part and choose to round up the prices with the largest fractional parts to reach the target while minimizing the rounding error. This is a classic greedy approach where rounding the largest fractional parts up minimizes the total error.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Generate all floor/ceil combinations; infeasible for n=500
Optimal	O(n log n)	O(n)	Greedy rounding by fractional parts to meet target

Algorithm Walkthrough

Convert each price string into a float for calculation purposes and separate it into its integer floor and fractional parts. The fractional part indicates the difference between the number and its floor.
Compute the sum of all floors, which represents the minimum sum achievable.
Compute the sum of all ceilings, which represents the maximum sum achievable.
Check if the target is achievable. If target < sum_floors or target > sum_ceilings, return "-1" immediately.
Count how many prices need to be rounded up (ceil_count) to meet the target exactly. This is target - sum_floors.
Sort the prices by their fractional parts in descending order, so that the numbers with the largest fractional parts are rounded up first. This minimizes the total rounding error.
Calculate the total rounding error by summing the differences. For each of the first ceil_count prices in the sorted order, add the ceiling error (1 - fractional_part). For the remaining prices, add the floor error (fractional_part).
Return the total rounding error formatted to three decimal places.

This approach works because rounding the largest fractional parts up introduces the smallest incremental error, and rounding the smallest fractional parts down adds the smallest possible error. The greedy choice of rounding the largest fractional parts up guarantees the minimum total rounding error while meeting the target.

Python Solution

from typing import List

class Solution:
    def minimizeError(self, prices: List[str], target: int) -> str:
        floors = []
        fractional_parts = []
        sum_floors = 0
        
        for price in prices:
            value = float(price)
            floor_val = int(value)
            frac = value - floor_val
            floors.append(floor_val)
            fractional_parts.append(frac)
            sum_floors += floor_val
        
        ceil_count = target - sum_floors
        if ceil_count < 0 or ceil_count > len(prices):
            return "-1"
        
        fractional_parts.sort(reverse=True)
        
        error = 0.0
        for i, frac in enumerate(fractional_parts):
            if i < ceil_count:
                error += 1 - frac if frac > 0 else 0
            else:
                error += frac
        
        return f"{error:.3f}"

The code first converts price strings into floats, computes the floor of each, and records the fractional parts. It checks if the target is achievable using the sum of floors. Then it calculates how many prices must be rounded up and sorts the fractional parts to greedily minimize error. Finally, it sums the rounding errors based on whether a price is rounded up or down.

Go Solution

import (
    "fmt"
    "sort"
    "strconv"
)

func minimizeError(prices []string, target int) string {
    n := len(prices)
    floors := make([]int, n)
    fractions := make([]float64, n)
    sumFloors := 0
    
    for i, p := range prices {
        value, _ := strconv.ParseFloat(p, 64)
        floorVal := int(value)
        frac := value - float64(floorVal)
        floors[i] = floorVal
        fractions[i] = frac
        sumFloors += floorVal
    }
    
    ceilCount := target - sumFloors
    if ceilCount < 0 || ceilCount > n {
        return "-1"
    }
    
    sort.Slice(fractions, func(i, j int) bool {
        return fractions[i] > fractions[j]
    })
    
    error := 0.0
    for i, frac := range fractions {
        if i < ceilCount {
            if frac > 0 {
                error += 1 - frac
            }
        } else {
            error += frac
        }
    }
    
    return fmt.Sprintf("%.3f", error)
}

In Go, the approach mirrors Python: parse strings into floats, compute floors and fractions, check if the target is achievable, and sort fractional parts. Go requires explicit float parsing and formatting using strconv and fmt.Sprintf.

Worked Examples

Example 1: prices = ["0.700","2.800","4.900"], target = 8

Price	Floor	Fraction	Rounded
0.700	0	0.7	Ceil → 1
2.800	2	0.8	Ceil → 3
4.900	4	0.9	Floor → 4

Sum of floors = 0+2+4=6

Target = 8 → ceil_count = 8-6 = 2

Sort fractions descending: 0.9, 0.8, 0.7

Round top 2 fractions up: 0.9→Ceil, 0.8→Ceil, 0.7→Floor

Rounding error: (1-0.7) + (3-2.8) + (4-4.9) = 0.3 + 0.2 + 0.9 = 1.0

Return "1.000"

Example 2: prices = ["1.500","2.500","3.500"], target = 10

Sum of floors = 1+2+3=6, Sum of ceilings = 2+3+4=9

Target = 10 → impossible

Return "-1"

Example 3: prices = ["1.500","2.500","3.500"], target = 9

Sum of floors = 6

Target = 9 → ceil_count = 3

Sort fractions descending: 0.5, 0.5, 0.5

Round top 3 fractions up → all rounded up

Rounding error = (2-1.5) + (3-2.5) + (4-3.5) = 0.5 + 0.5 + 0.5 = 1.5

Return "1.500"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting fractional parts dominates
Space	O(n)	Store floors and fractions arrays

The time complexity is dominated by sorting the fractional parts. All other operations are linear in the number of prices. Space complexity is linear because we store arrays for floors and fractions.

Test Cases

# Basic examples
assert Solution().minimizeError(["0.700","2.800","4.900"], 8) == "1.000"  # Example 1
assert Solution().minimizeError(["1.500","2.500","3.500"], 10) == "-1"    # Example 2
assert Solution().minimizeError(["1.500","2.500","3.500"], 9) == "1.500"  # Example 3

# Edge cases
assert Solution().minimizeError(["0.000"], 0)