Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1058.html

1058. Minimize Rounding Error to Meet Target

Level

Medium

Description

Given an array of prices [p_1,p_2...,p_n] and a target, round each price p_i to Round_i(p_i) so that the rounded array [Round_1(p_1),Round_2(p_2)...,Round_n(p_n)] sums to the given target. Each operation Round_i(p_i) could be either Floor(p_i) or Ceil(p_i).

Return the string "-1" if the rounded array is impossible to sum to target. Otherwise, return the smallest rounding error, which is defined as Σ Roundi(pi) - (pi) for i from 1 to n, as a string with three places after the decimal.

Example 1:

Input: prices = [“0.700”,”2.800”,”4.900”], target = 8

Output: “1.000”

Explanation:

Use Floor, Ceil and Ceil operations to get (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = 0.7 + 0.2 + 0.1 = 1.0 .

Example 2:

Input: prices = [“1.500”,”2.500”,”3.500”], target = 10

Output: “-1”

Explanation:

It is impossible to meet the target.

Note:

  1. 1 <= prices.length <= 500.
  2. Each string of prices prices[i] represents a real number which is between 0 and 1000 and has exactly 3 decimal places.
  3. target is between 0 and 1000000.

Solution

Since each price in prices has exactly 3 decimal places, multiply each price and target by 1000 to make all the numbers become integers. Do floor operation on all prices to obtain the smallest possible sum, and do ceiling operation on all prices to obtain the greatest possible sum. If target is not in the range, return "-1".

Calculate the difference between target and the smallest possible sum, and obtain the number of prices that need to be changed to ceiling operation. The prices with greater remainders when divided by 1000 (or greater fraction part before multiplied by 1000) should be considered first so that the rounding error can be reduced the most. Use a priority queue to store all the prices, where the prices with greater remainders when divided by 1000 are polled first. Each time poll a price and change the floor operation to ceiling operation, and update the rounding error. Repeat the process until target is met. Finally, return the rounding error.

  • class Solution {
    public String minimizeError(String[] prices, int target) {
        int length = prices.length;
        int[] priceArray = new int[length];
        int[] minArray = new int[length];
        int[] maxArray = new int[length];
        int minSum = 0, maxSum = 0, errorSum = 0;
        for (int i = 0; i < length; i++) {
            String priceStr = prices[i];
            int pointIndex = priceStr.indexOf('.');
            String iPart = priceStr.substring(0, pointIndex);
            String fPart = priceStr.substring(pointIndex + 1);
            int price = Integer.parseInt(iPart) * 1000 + Integer.parseInt(fPart);
            priceArray[i] = price;
            if (price % 1000 == 0) {
                minArray[i] = price;
                maxArray[i] = price;
            } else {
                minArray[i] = price / 1000 * 1000;
                maxArray[i] = minArray[i] + 1000;
            }
            minSum += minArray[i];
            maxSum += maxArray[i];
            errorSum += price - minArray[i];
        }
        int targetThousand = target * 1000;
        if (targetThousand > maxSum || targetThousand < minSum)
            return "-1";
        int difference = targetThousand - minSum;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 % 1000 - num1 % 1000;
            }
        });
        for (int i = 0; i < length; i++)
            priorityQueue.offer(priceArray[i]);
        for (int i = 0; i < difference; i += 1000) {
            int price = priorityQueue.poll();
            int remainder = price % 1000;
            int newRemainder = 1000 - remainder;
            errorSum -= (remainder - newRemainder);
        }
        String minErrorIPart = String.valueOf(errorSum / 1000);
        String minErrorFPart = String.format("%03d", errorSum % 1000);
        String minError = minErrorIPart + "." + minErrorFPart;
        return minError;
    }
}

  • class Solution:
    def minimizeError(self, prices: List[str], target: int) -> str:
        mi = 0
        arr = []
        for p in prices:
            p = float(p)
            mi += int(p)
            if d := p - int(p):
                arr.append(d)
        if not mi <= target <= mi + len(arr):
            return "-1"
        d = target - mi
        arr.sort(reverse=True)
        ans = d - sum(arr[:d]) + sum(arr[d:])
        return f'{ans:.3f}'



  • class Solution {
public:
    string minimizeError(vector<string>& prices, int target) {
        int mi = 0;
        vector<double> arr;
        for (auto& p : prices) {
            double price = stod(p);
            mi += (int) price;
            double d = price - (int) price;
            if (d > 0) {
                arr.push_back(d);
            }
        }
        if (target < mi || target > mi + arr.size()) {
            return "-1";
        }
        int d = target - mi;
        sort(arr.rbegin(), arr.rend());
        double ans = d;
        for (int i = 0; i < d; ++i) {
            ans -= arr[i];
        }
        for (int i = d; i < arr.size(); ++i) {
            ans += arr[i];
        }
        string s = to_string(ans);
        return s.substr(0, s.find('.') + 4);
    }
};

  • func minimizeError(prices []string, target int) string {
	arr := []float64{}
	mi := 0
	for _, p := range prices {
		price, _ := strconv.ParseFloat(p, 64)
		mi += int(math.Floor(price))
		d := price - float64(math.Floor(price))
		if d > 0 {
			arr = append(arr, d)
		}
	}
	if target < mi || target > mi+len(arr) {
		return "-1"
	}
	d := target - mi
	sort.Float64s(arr)
	ans := float64(d)
	for i := 0; i < d; i++ {
		ans -= arr[len(arr)-i-1]
	}
	for i := d; i < len(arr); i++ {
		ans += arr[len(arr)-i-1]
	}
	return fmt.Sprintf("%.3f", ans)
}

All Problems

All Solutions