## Minimize Rounding Error to Meet Target

• Time:O(n\log n)
• Space:O(n)

## C++

``````class Solution {
public:
string minimizeError(vector<string>& prices, int target) {
// A[i] := (costCeil - costFloor, costCeil, costFloor)
// the lower the costCeil - costFloor, the cheaper to ceil it
vector<tuple<double, double, double>> A;
int sumFloored = 0;
int sumCeiled = 0;

for (const auto& 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";

sort(begin(A), end(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();
}
};
``````

## JAVA

``````class Solution {
public String minimizeError(String[] prices, int target) {
// A[i] := (costCeil - costFloor, costCeil, costFloor)
// the lower the costCeil - costFloor, 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);
}
}
``````

## Python

``````class Solution:
def minimizeError(self, prices: List[str], target: int) -> str:
# A[i] := (costCeil - costFloor, costCeil, costFloor)
# the lower the costCeil - costFloor, 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:]))
``````