Code Implementation

from typing import List

class Solution:
    def minimizeError(self, prices: List[str], target: int) -> str:
        import math
        n = len(prices)
        floors = []
        ceils = []
        total_floor = 0
        non_integer_count = 0
        diffs = []
        for p in prices:
            f = math.floor(float(p))
            c = math.ceil(float(p))
            total_floor += f
            if f != c:
                non_integer_count += 1
                diffs.append(float(p) - f)
            floors.append(f)
            ceils.append(c)
        # To reach target, need to ceil k prices and floor the rest
        ceil_count = target - total_floor
        if ceil_count < 0 or ceil_count > non_integer_count:
            return "-1"
        # Sort the fractional parts, smallest first
        diffs.sort()
        # To minimize error, ceil the ceil_count with largest diffs
        error = 0
        idx = 0
        for p in prices:
            f = math.floor(float(p))
            c = math.ceil(float(p))
            if f == c:
                # Already integer
                error += 0
            else:
                # Will decide later
                pass
        # Ceil ceil_count largest diffs (i.e., smallest fractional parts are floored)
        error = 0
        sorted_diffs = sorted([float(p) - math.floor(float(p)) for p in prices if math.floor(float(p)) != math.ceil(float(p))])
        for i, d in enumerate(sorted_diffs):
            if i < len(sorted_diffs) - ceil_count:
                error += d
            else:
                error += 1 - d
        return "{0:.3f}".format(error)
      

#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <sstream>

using namespace std;

class Solution {
public:
    string minimizeError(vector<string>& prices, int target) {
        int n = prices.size();
        int total_floor = 0;
        int non_integer_count = 0;
        vector<double> diffs;
        for (const string& p : prices) {
            double val = stod(p);
            int f = floor(val);
            int c = ceil(val);
            total_floor += f;
            if (f != c) {
                non_integer_count++;
                diffs.push_back(val - f);
            }
        }
        int ceil_count = target - total_floor;
        if (ceil_count < 0 || ceil_count > non_integer_count) {
            return "-1";
        }
        sort(diffs.begin(), diffs.end());
        double error = 0;
        for (int i = 0; i < diffs.size(); ++i) {
            if (i < (int)diffs.size() - ceil_count) {
                error += diffs[i];
            } else {
                error += 1 - diffs[i];
            }
        }
        stringstream ss;
        ss << fixed << setprecision(3) << error;
        return ss.str();
    }
};
      

import java.util.*;

class Solution {
    public String minimizeError(String[] prices, int target) {
        int n = prices.length;
        int totalFloor = 0;
        int nonIntegerCount = 0;
        List<Double> diffs = new ArrayList<>();
        for (String p : prices) {
            double val = Double.parseDouble(p);
            int f = (int)Math.floor(val);
            int c = (int)Math.ceil(val);
            totalFloor += f;
            if (f != c) {
                nonIntegerCount++;
                diffs.add(val - f);
            }
        }
        int ceilCount = target - totalFloor;
        if (ceilCount < 0 || ceilCount > nonIntegerCount) {
            return "-1";
        }
        Collections.sort(diffs);
        double error = 0;
        for (int i = 0; i < diffs.size(); ++i) {
            if (i < diffs.size() - ceilCount) {
                error += diffs.get(i);
            } else {
                error += 1 - diffs.get(i);
            }
        }
        return String.format("%.3f", error);
    }
}
      

/**
 * @param {string[]} prices
 * @param {number} target
 * @return {string}
 */
var minimizeError = function(prices, target) {
    let n = prices.length;
    let totalFloor = 0;
    let nonIntegerCount = 0;
    let diffs = [];
    for (let p of prices) {
        let val = parseFloat(p);
        let f = Math.floor(val);
        let c = Math.ceil(val);
        totalFloor += f;
        if (f !== c) {
            nonIntegerCount++;
            diffs.push(val - f);
        }
    }
    let ceilCount = target - totalFloor;
    if (ceilCount < 0 || ceilCount > nonIntegerCount) {
        return "-1";
    }
    diffs.sort((a, b) => a - b);
    let error = 0;
    for (let i = 0; i < diffs.length; ++i) {
        if (i < diffs.length - ceilCount) {
            error += diffs[i];
        } else {
            error += 1 - diffs[i];
        }
    }
    return error.toFixed(3);
};
      

Problem Description

Given a list of prices as strings prices, and an integer target, you must round each price either up (ceil) or down (floor) to an integer. The sum of these rounded values must equal target. Your task is to minimize the total rounding error, which is the sum of the absolute differences between the original price and its rounded value, across all prices.

If it is impossible to achieve the target by rounding in this way, return "-1". Otherwise, return the minimum total rounding error, formatted with exactly 3 decimal places.

• Each price is a string with exactly 3 decimal places (e.g., "0.700").
• All rounding decisions must be made independently for each price.
• There is at least one valid solution if possible, but not all prices are integers.

Thought Process

At first, you might think of brute-forcing all possible ways to round each price up or down, checking which combinations sum to the target, and picking the one with the smallest total error. However, this is not feasible for large inputs because the number of combinations grows exponentially with the number of prices.

Instead, let's break down the problem:

• For each price, rounding down (floor) or up (ceil) gives two possible integer values.
• Some prices are already integers, so rounding doesn't affect them.
• For non-integer prices, we need to decide which ones to round up (ceil) so that the total sum matches the target.

This transforms the problem into a selection problem: choose which prices to round up so that the sum matches the target, and do it in a way that minimizes error.

Solution Approach

Let's break down the solution step by step:

1. Identify integer and non-integer prices:
   • If a price is already an integer, rounding it up or down doesn't matter.
   • If not, it has a fractional part between 0 and 1.
2. Compute the minimal sum from rounding all non-integers down (floor):
   • Sum the floor of every price. This is the lowest possible sum you can get by rounding down everywhere.
3. Determine how many prices must be rounded up:
   • Let ceil_count = target - total_floor. This is the number of non-integer prices that must be rounded up to reach the target.
   • If ceil_count is negative or greater than the number of non-integer prices, it's impossible.
4. Minimize error by choosing which prices to round up:
   • For each non-integer price, the rounding error is either fractional part (if floored) or 1 - fractional part (if ceiled).
   • To minimize error, round up the ceil_count prices with the largest fractional parts, and round down the rest.
   • This is because 1 - x < x when x > 0.5, so it's better to ceil those with large fractions.
5. Calculate total error:
   • Sum the errors for all prices, using 0 for integers, fractional part for floored, and 1 - fractional part for ceiled.
6. Format the answer:
   • Return the result as a string with exactly three decimal places.

Example Walkthrough

Suppose prices = ["0.700", "2.800", "4.900"] and target = 8.

1. Floor values:
   • 0.700 → 0
   • 2.800 → 2
   • 4.900 → 4

   Total floor sum = 0 + 2 + 4 = 6

2. Non-integer prices: All are non-integers.
3. How many to round up?
   • ceil_count = 8 - 6 = 2

   We must round up 2 of the 3 prices.

4. Fractional parts:
   • 0.700: 0.7
   • 2.800: 0.8
   • 4.900: 0.9
5. Sort fractional parts: [0.7, 0.8, 0.9]
6. Round up the two largest: 0.8 and 0.9 (so, ceil 2.800 and 4.900), floor 0.700.
7. Calculate error:
   • 0.700 floored: error = 0.7
   • 2.800 ceiled: error = 1 - 0.8 = 0.2
   • 4.900 ceiled: error = 1 - 0.9 = 0.1

   Total error = 0.7 + 0.2 + 0.1 = 1.0

8. Return: "1.000"

Time and Space Complexity

Brute-force approach:

• Would try all 2ⁿ combinations (for n prices), so time complexity is O(2ⁿ).
• Space complexity is O(n) for recursion stack or storing combinations.

• We process each price once (O(n)), and sort the fractional parts (O(n log n)).
• Total time complexity: O(n log n) due to the sort.
• Space complexity: O(n) for storing fractional parts.

Summary

The key to this problem is recognizing that for each non-integer price, rounding up or down affects both the sum and the error. By always rounding up the prices with the largest fractional parts (and rounding the rest down), we can guarantee both that the sum matches the target and that the total error is minimized. This greedy approach is both efficient and elegant, reducing the problem to simple sorting and selection.