We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimize Rounding Error to Meet Target

Number: 1053

Difficulty: Medium

Paid? Yes

Companies: Airbnb

Problem Description

We are given an array of price strings and a target value. For each price, we can round down (Floor) or round up (Ceil). The rounded numbers must sum exactly to the target, and we need to minimize the total rounding error defined as the sum of absolute differences between the original price and the rounded value. If it is impossible to achieve the target sum with any combination of rounds, return "-1". Otherwise, return the minimum total rounding error as a string formatted to three decimal places.

Key Insights

  • Compute the floor value for each price and its associated fractional part.
  • The sum of all floor values represents the minimum achievable sum.
  • The number of prices with a non-zero fractional part gives the maximum options for rounding up.
  • The difference between the target and the floor sum tells exactly how many prices need to be rounded up.
  • Rounding up a price introduces an error adjustment of (1 - 2*fractional part) when compared to leaving it floored.
  • To minimize error, sort the fractional parts and choose the smallest ones for rounding up.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the fractional parts
Space Complexity: O(n) for storing the fractional parts

Solution

First, iterate through the prices, converting each to a floating-point number. Compute its floor value, add it to the running floor sum, and store its fractional part (if non-zero). The difference between the target and the floor sum tells you how many rounding up operations are needed. If this difference is negative or larger than the number of numbers with fractional parts, it is impossible to meet the target. Otherwise, sort the fractional parts in ascending order; using the smallest ones for rounding up minimizes the additional error incurred. Adjust the total error accordingly and return the result formatted to three decimal places.

Code Solutions

# Python solution
def minimizeError(prices, target):
    floor_sum = 0
    fractional_errors = []
    
    # Calculate total floor values and record fractional parts
    for p_str in prices:
        p = float(p_str)
        floor_val = int(p)  # Floor value
        floor_sum += floor_val
        frac = p - floor_val
        if frac != 0:
            fractional_errors.append(frac)
    
    diff = target - floor_sum
    # If rounding is impossible (too many or too few ups)
    if diff < 0 or diff > len(fractional_errors):
        return "-1"
    
    # Sort fractional parts: smallest ones yield minimal extra error when rounded up
    fractional_errors.sort()
    
    # Total error when rounding down each non-integer
    total_error = sum(fractional_errors)
    
    # For diff numbers that we round up, subtract fractional part error and add (1 - frac)
    for i in range(diff):
        total_error += (1 - 2 * fractional_errors[i])
    
    return "{:.3f}".format(total_error)

# Example usage:
print(minimizeError(["0.700", "2.800", "4.900"], 8))   # Expected output: "1.000"
print(minimizeError(["1.500", "2.500", "3.500"], 10))    # Expected output: "-1"
print(minimizeError(["1.500", "2.500", "3.500"], 9))     # Expected output: "1.500"
← Back to All Questions