Skip to main content
Talentd

Minimize Rounding Error to Meet Target - Solution & Explanation

MediumPremiumFree on FleetCodeArrayMathStringGreedy5 min readAsked at: Airbnb
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You receive prices as decimal strings. Each value can be rounded either down (floor) or up (ceil). The goal is to choose rounding directions so the total equals a given integer target while minimizing the total rounding error.

Approach 1: Greedy with Sorting (O(n log n) time, O(n) space)

Start by converting each string to a number and computing its floor and ceil. If a value is already an integer, both operations give the same result and must be used as-is. Compute floorSum and ceilSum across the array. If the target is outside this range, no combination of rounding operations can reach it.

The key decision is how many numbers must be rounded up. That value is k = target - floorSum. Initially assume every non-integer is rounded down, which produces error equal to its fractional part. Rounding up changes the error to 1 - fraction. The extra cost of switching from down to up is (1 - fraction) - fraction. Sort numbers by this extra cost and choose the k smallest values to round up. This greedy choice minimizes total error because the numbers closest to the next integer have the cheapest upward rounding cost. The algorithm relies on simple arithmetic and sorting from math and sorting.

Approach 2: Greedy with Heap (O(n log n) time, O(n) space)

Instead of sorting the entire list, push the cost difference for each non-integer price into a min-heap. After computing k = target - floorSum, pop the smallest k costs and treat those numbers as rounded up. The rest remain rounded down. This produces the same result as sorting but can be easier to implement if you prefer incremental selection logic.

Both strategies rely on the same greedy observation: rounding up numbers with the largest fractional parts produces the smallest additional error. The heap version emphasizes selection, while the sorting version keeps the logic simpler.

Recommended for interviews: The greedy sorting approach is the expected solution. It demonstrates understanding of rounding boundaries, feasibility checks, and cost-based greedy decisions. Interviewers often want to see the reasoning behind computing k = target - floorSum and why sorting fractional costs guarantees minimal total error. This pattern frequently appears in greedy optimization problems.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor β†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with SortingO(n log n)O(n)General case. Simple implementation and the most common interview solution.
Greedy with Min HeapO(n log n)O(n)Useful when selecting the k smallest rounding costs without sorting the entire array.

Video Solution

ηŒ©ηŒ©ηš„δΉε›­ LeetCode 1058 Minimize Rounding Error to Meet Target β€’ ηŒ©ηŒ©ηš„δΉε›­ β€’ 601 views views

Watch 2 more video solutions β†’

Frequently Asked Questions

Is Minimize Rounding Error to Meet Target easy or hard?
The problem is rated Medium because the greedy insight is not obvious at first. You must recognize the feasibility range using floor and ceil sums, then convert the objective into minimizing cost differences when selecting which numbers to round up.
Minimize Rounding Error to Meet Target Python/Java solution
Implementations in Python, Java, and C++ follow the same steps: parse the string prices, compute floorSum, determine k = target - floorSum, store rounding cost differences, sort them, and sum the minimal total error. The final answer is typically formatted to three decimal places.
How to solve Minimize Rounding Error to Meet Target in O(n)?
Pure O(n) solutions are uncommon because selecting the optimal k rounding candidates typically requires sorting or a priority structure. The standard approach sorts fractional costs in O(n log n). A linear-time variant would require selection algorithms like quickselect to find the k smallest costs, but that is rarely implemented in interviews.
What is the best approach for Minimize Rounding Error to Meet Target?
The best approach is a greedy strategy that sorts numbers by the cost difference between rounding up and rounding down. First compute the sum of all floors and determine how many numbers must be rounded up (k = target - floorSum). Then choose the k numbers with the smallest additional cost when rounded up. This runs in O(n log n) time due to sorting.
Is Minimize Rounding Error to Meet Target asked at Google/Amazon/Meta?
Rounding optimization and greedy cost selection problems appear in interviews at companies like Google and Amazon. This problem tests numeric reasoning, feasibility checks, and greedy selection logic, which are common patterns in backend and systems-focused interviews.
What data structure is used in Minimize Rounding Error to Meet Target?
The solution primarily uses arrays to store fractional rounding costs and either sorting or a min-heap (priority queue) to select the cheapest elements to round up. The heap version helps extract the k smallest costs efficiently.
What is the time complexity of Minimize Rounding Error to Meet Target?
The optimal solution runs in O(n log n) time because it sorts the rounding cost differences for all non-integer prices. Each price is processed once to compute floor and ceil values. Space complexity is O(n) to store fractional costs and intermediate values.

Ready to solve this problem?

Practice Minimize Rounding Error to Meet Target with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays