Skip to content

1058. Minimize Rounding Error to Meet Target

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  string minimizeError(vector<string>& prices, int target) {
    // A[i] := (costCeil - costFloor, costCeil, costFloor)
    // The lower the costCeil - costFloor is, the cheaper to ceil it.
    vector<tuple<double, double, double>> A;
    int sumFloored = 0;
    int sumCeiled = 0;

    for (const string& p : prices) {
      const double price = stod(p);
      const int floored = floor(price);
      const int ceiled = ceil(price);
      sumFloored += floored;
      sumCeiled += ceiled;
      const double costFloor = price - static_cast<double>(floored);
      const double costCeil = static_cast<double>(ceiled) - price;
      A.emplace_back(costCeil - costFloor, costCeil, costFloor);
    }

    if (sumFloored > target || sumCeiled < target)
      return "-1";

    ranges::sort(A);

    double sumError = 0.0;
    const int nCeiled = target - sumFloored;
    for (int i = 0; i < nCeiled; ++i)
      sumError += get<1>(A[i]);
    for (int i = nCeiled; i < A.size(); ++i)
      sumError += get<2>(A[i]);

    stringstream ss;
    ss << std::fixed << std::setprecision(3) << sumError;
    return ss.str();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
  public String minimizeError(String[] prices, int target) {
    // A[i] := (costCeil - costFloor, costCeil, costFloor)
    // The lower the costCeil - costFloor is, the cheaper to ceil it.
    List<double[]> A = new ArrayList<>();
    int sumFloored = 0;
    int sumCeiled = 0;

    for (final String p : prices) {
      final double price = Double.parseDouble(p);
      final int floored = (int) Math.floor(price);
      final int ceiled = (int) Math.ceil(price);
      sumFloored += floored;
      sumCeiled += ceiled;
      final double costFloor = price - (double) floored;
      final double costCeil = (double) ceiled - price;
      A.add(new double[] {costCeil - costFloor, costCeil, costFloor});
    }

    if (sumFloored > target || sumCeiled < target)
      return "-1";

    Collections.sort(A, new Comparator<double[]>() {
      @Override
      public int compare(double[] a, double[] b) {
        return Double.compare(a[0], b[0]);
      }
    });

    double sumError = 0.0;
    final int nCeiled = target - sumFloored;
    for (int i = 0; i < nCeiled; ++i)
      sumError += A.get(i)[1];
    for (int i = nCeiled; i < A.size(); ++i)
      sumError += A.get(i)[2];

    return String.format("%.3f", sumError);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def minimizeError(self, prices: list[str], target: int) -> str:
    # A[i] := (costCeil - costFloor, costCeil, costFloor)
    # The lower the costCeil - costFloor is, the cheaper to ceil it.
    A = []
    sumFloored = 0
    sumCeiled = 0

    for price in map(float, prices):
      floored = math.floor(price)
      ceiled = math.ceil(price)
      sumFloored += floored
      sumCeiled += ceiled
      costFloor = price - floored
      costCeil = ceiled - price
      A.append((costCeil - costFloor, costCeil, costFloor))

    if not sumFloored <= target <= sumCeiled:
      return '-1'

    A.sort()
    nCeiled = target - sumFloored
    return '{:.3f}'.format(sum(a[1] for a in A[:nCeiled]) +
                           sum(a[2] for a in A[nCeiled:]))