Minimize rounding error to meet target

Array Math String Greedy Sorting

45.8% acceptance

Mar 31, 2026

157

149

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimize_error(prices: Vec<String>, target: i32) -> String {
    let mut fracs: Vec<f64> = Vec::new();
    let mut sum_floor: i32 = 0;
    let mut count_non_zero = 0;
    for p in &prices {
      let val: f64 = p.parse().unwrap();
      let floor = val.floor() as i32;
      let frac = val - floor as f64;
      sum_floor += floor;
      fracs.push(frac);
      if frac > 1e-9 { count_non_zero += 1; }
    }
    let needed = target - sum_floor;
    if needed < 0 || needed > count_non_zero {
      return "-1".to_string();
    }
    // To minimize error, ceil those with highest frac (1-frac is smallest)
    fracs.sort_by(|a, b| b.partial_cmp(a).unwrap());
    let mut total_error = 0.0f64;
    for (i, &frac) in fracs.iter().enumerate() {
      if (i as i32) < needed {
        total_error += 1.0 - frac; // ceil error
      } else {
        total_error += frac; // floor error
      }
    }
    format!("{:.3}", total_error)
  }
}