Problem Description

You are given an array of prices (as strings) and a target sum. Each price needs to be rounded to either its floor or ceiling value, and the sum of all rounded prices must equal the target.

The goal is to minimize the total rounding error, which is calculated as the sum of absolute differences between each rounded value and its original value: Σ |Round(pi) - pi|.

Key constraints:

• Each price pi can only be rounded to Floor(pi) or Ceil(pi)
• The sum of all rounded prices must exactly equal the target
• If it's impossible to achieve the target sum through any combination of floor/ceiling operations, return "-1"
• If a valid solution exists, return the minimum rounding error as a string with exactly 3 decimal places

Example breakdown:

• If you have prices [1.5, 2.3, 3.7] and target 7:
  • Possible rounding: [1, 2, 4] → sum = 7 ✓
  • Rounding error: |1-1.5| + |2-2.3| + |4-3.7| = 0.5 + 0.3 + 0.3 = 1.1
  • Return: "1.100"

The challenge is to determine which prices to round down (floor) and which to round up (ceiling) to achieve the exact target sum while minimizing the total rounding error.

Intuition

To find the minimum rounding error, let's first understand the bounds of what's possible. If we round all prices down (floor), we get the minimum possible sum. If we round all prices up (ceiling), we get the maximum possible sum. The target must fall within this range for a solution to exist.

The key insight is that rounding a number with a decimal part causes different errors depending on the direction:

• Rounding down from x.d to x creates an error of d
• Rounding up from x.d to x+1 creates an error of 1-d

For integers (no decimal part), there's no choice - we must keep them as is with zero error.

Now, if we start with all prices floored, we need to selectively round some up to reach the target. Each time we change a floor to a ceiling, we:

• Increase the sum by 1
• Change the error from d to 1-d

The net change in error is (1-d) - d = 1-2d. To minimize total error, we should prioritize rounding up the numbers with the largest decimal parts (largest d values), as this gives us the most negative change in error (1-2d).

This leads to a greedy strategy:

1. Start with all numbers floored and calculate how many need to be ceiled to reach the target
2. Sort the decimal parts in descending order
3. Round up the numbers with the largest decimal parts first
4. The final error is the sum of (1-d) for rounded up numbers plus the sum of d for rounded down numbers

Learn more about Greedy, Math and Sorting patterns.

Solution Approach

Let's walk through the implementation step by step:

Step 1: Extract decimal parts and calculate bounds

mi = 0
arr = []
for p in prices:
    p = float(p)
    mi += int(p)  # Sum of all floors
    if d := p - int(p):  # Extract decimal part
        arr.append(d)

• Convert each price string to float
• mi accumulates the sum of all floored values (minimum possible sum)
• arr collects all non-zero decimal parts (these are the prices we can choose to round up)

Step 2: Check feasibility

if not mi <= target <= mi + len(arr):
    return "-1"

• The minimum sum is mi (all floored)
• The maximum sum is mi + len(arr) (all non-integers rounded up)
• If target is outside this range, it's impossible to achieve

Step 3: Determine how many to round up

d = target - mi

• Since we start with all floored (sum = mi), we need to round up exactly d numbers to reach the target
• Each rounding up increases the sum by 1

Step 4: Greedy selection

arr.sort(reverse=True)
ans = d - sum(arr[:d]) + sum(arr[d:])

• Sort decimal parts in descending order
• Round up the d largest decimal parts (first d elements)
• Calculate total error:
  • For rounded up numbers (arr[:d]): error = 1 - decimal_part for each
  • Sum of errors = d - sum(arr[:d])
  • For rounded down numbers (arr[d:]): error = decimal_part for each
  • Sum of errors = sum(arr[d:])
  • Total error = d - sum(arr[:d]) + sum(arr[d:])

Step 5: Format result

return f'{ans:.3f}'

• Return the minimum error formatted to 3 decimal places

The algorithm runs in O(n log n) time due to sorting, with O(n) space for storing decimal parts.

Example Walkthrough

Let's walk through the solution with prices = ["2.700", "3.400", "5.900"] and target = 11.

Step 1: Extract decimal parts and calculate bounds

• Convert to floats: [2.7, 3.4, 5.9]
• Extract floors and decimal parts:
  • 2.7 → floor = 2, decimal = 0.7
  • 3.4 → floor = 3, decimal = 0.4
  • 5.9 → floor = 5, decimal = 0.9
• mi (sum of floors) = 2 + 3 + 5 = 10
• arr (decimal parts) = [0.7, 0.4, 0.9]

Step 2: Check feasibility

• Minimum possible sum = 10 (all floored)
• Maximum possible sum = 10 + 3 = 13 (all ceiled)
• Target = 11 is within [10, 13] ✓

Step 3: Determine how many to round up

• We need: target - mi = 11 - 10 = 1
• So we must round up exactly 1 number

Step 4: Greedy selection

• Sort decimal parts descending: [0.9, 0.7, 0.4]
• Round up the 1 largest decimal (0.9):
  • 5.9 → 6 (round up), error = |6 - 5.9| = 0.1
• Keep others floored:
  • 2.7 → 2 (round down), error = |2 - 2.7| = 0.7
  • 3.4 → 3 (round down), error = |3 - 3.4| = 0.4

Calculate total error:

• Using the formula: d - sum(arr[:d]) + sum(arr[d:])
• = 1 - sum([0.9]) + sum([0.7, 0.4])
• = 1 - 0.9 + 1.1
• = 1.2

Step 5: Format result

• Return "1.200"

Verification:

• Rounded values: [2, 3, 6]
• Sum: 2 + 3 + 6 = 11 ✓ (matches target)
• Total error: 0.7 + 0.4 + 0.1 = 1.2 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the length of the prices array.

• Converting each price string to float and calculating the floor value takes O(n) time
• Building the array of decimal parts takes O(n) time
• Sorting the decimal parts array takes O(k log k) time where k ≤ n is the number of non-integer prices
• Computing the sum of subarrays takes O(k) time
• Since k ≤ n, the dominant operation is sorting, giving us O(n log n) overall

Space Complexity: O(n)

• The arr list stores at most n decimal parts, requiring O(n) space
• Other variables (mi, d, ans) use constant space O(1)
• The sorting operation may use O(log n) space for the recursive call stack (depending on the implementation)
• Overall space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Floating Point Precision Issues

One of the most common pitfalls in this problem is dealing with floating-point arithmetic inaccuracies. When converting strings to floats and performing calculations, small precision errors can accumulate.

Problem Example:

price = "0.1"
p = float(price)  # 0.1
floor_val = int(p)  # 0
decimal = p - floor_val  # Might be 0.09999999999999998 instead of 0.1

Solution: Use the decimal module for precise arithmetic or round intermediate calculations appropriately:

from decimal import Decimal, ROUND_HALF_UP

price = Decimal("0.1")
floor_val = int(price)
decimal_part = price - floor_val  # Exactly 0.1

2. Integer Prices Handling

The code might incorrectly handle prices that are already integers (like "5.000" or "3").

Problem Example:

price = "5.000"
p = float(price)  # 5.0
decimal = p - int(p)  # 0.0
if decimal:  # This condition fails, but "5.000" could still be in prices array
    arr.append(decimal)

Solution: Be explicit about checking for near-zero decimals:

decimal_part = price_float - floor_value
if decimal_part > 1e-9:  # Use epsilon comparison
    decimal_parts.append(decimal_part)

3. Incorrect Target Feasibility Check

A subtle bug can occur when all prices are integers. The maximum sum calculation assumes we can only increase the sum by the count of non-integer prices.

Problem Example:

prices = ["1", "2", "3"]  # All integers
target = 7
# decimal_parts = [] (empty)
# min_sum = 6, max_sum = 6 + 0 = 6
# Returns "-1" even though target 7 might seem unreachable

This is actually correct behavior, but developers might misunderstand that integer prices cannot be "rounded up" since ceil(integer) = integer.

4. String Formatting Edge Cases

The final formatting might produce unexpected results for very small errors.

Problem Example:

total_error = 0.0005
return f'{total_error:.3f}'  # Returns "0.001" due to rounding

Solution: Consider whether you want banker's rounding or always round down for consistency:

import math
# To always round down to 3 decimals:
truncated = math.floor(total_error * 1000) / 1000
return f'{truncated:.3f}'

5. Empty Decimal Parts Array

When all prices are integers, sorting an empty array and slicing it could cause issues in some implementations.

Problem Example:

decimal_parts = []
decimal_parts.sort(reverse=True)  # OK, but empty
sum(decimal_parts[:0])  # Returns 0, which is correct
sum(decimal_parts[0:])  # Returns 0, which is correct

While Python handles this gracefully, it's worth adding an early check:

if not decimal_parts and target != min_sum:
    return "-1"
if not decimal_parts:
    return "0.000"