Welcome to Subscribe On Youtube

1058. Minimize Rounding Error to Meet Target

Description

Given an array of prices [p1,p2...,pn] and a target, round each price pi to Roundi(pi) so that the rounded array [Round1(p1),Round2(p2)...,Roundn(pn)] sums to the given target. Each operation Roundi(pi) could be either Floor(pi) or Ceil(pi).

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.

Example 3:

Input: prices = ["1.500","2.500","3.500"], target = 9
Output: "1.500"

 

Constraints:

• 1 <= prices.length <= 500
• Each string prices[i] represents a real number in the range [0.0, 1000.0] and has exactly 3 decimal places.
• 0 <= target <= 106

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public String minimizeError(String[] prices, int target) {
          int mi = 0;
          List<Double> arr = new ArrayList<>();
          for (String p : prices) {
              double price = Double.valueOf(p);
              mi += (int) price;
              double d = price - (int) price;
              if (d > 0) {
                  arr.add(d);
              }
          }
          if (target < mi || target > mi + arr.size()) {
              return "-1";
          }
          int d = target - mi;
          arr.sort(Collections.reverseOrder());
          double ans = d;
          for (int i = 0; i < d; ++i) {
              ans -= arr.get(i);
          }
          for (int i = d; i < arr.size(); ++i) {
              ans += arr.get(i);
          }
          DecimalFormat df = new DecimalFormat("#0.000");
          return df.format(ans);
      }
  }
  

• 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);
      }
  };
  

• 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}'
  
  

• 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