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.

Description Hints 3 Solution Video 8:38

1058. Minimize Rounding Error to Meet Target

Medium45.9% acceptance1 companyPremium elsewhere, free here

Given an array of prices [p₁,p₂...,p_n] and a target, round each price p_i to Round_i(p_i) so that the rounded array [Round₁(p₁),Round₂(p₂)...,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 Σ |Round_i(p_i) - (p_i)| 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 <= 10⁶

Asked at 1 company

Airbnb

Topics

Hints open one at a time

Hint 1

If we have integer values in the array then we just need to subtract the target those integer values, so we reduced the problem.

Hint 2

Similarly if we have non integer values we have two options to put them flor(value) or ceil(value) = floor(value) + 1, so the idea is to just subtract floor(value).

Hint 3

Now the problem is different for each position we can sum just add 0 or 1 in order to sum the target, minimizing the deltas. This can be solved with DP.

8:38

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

["0.700","2.800","4.900"]
8

Input

["1.500","2.500","3.500"]
10

Input

["1.500","2.500","3.500"]
9

Your code is saved on this device.Solution