This post is completed by 1 user

  • 0
 Add to List
Hard

399. Round Price Problem

Problem Statement:
When customers book an Airbnb the total price, which includes base price + service fee + cleaning fee. 
all these prices are in decimals.
Write an algorithm to round each price such that the sum of the prices equals the round of the total sum of all decimal prices and minimize the rounding.
Given:
An array of numbers A = [x1, x2, ..., xn] and Target = Round(x1+x2+... +xn)
where x1, x2,..xn are different charges to customers like base price, service fee and so on.

Objective: Write an algorithm to round each element in A such that after rounding we get a new array B = [y1, y2, ...., yn] such that y1 + y2 +...+ yn = Target where yi = Floor(xi) or Ceil(xi), ceiling or floor of xi. Also Minimize minimize sum (|x1-y1| + |x2-y2| +.....+ |xn-yn|)

Example:

input = 30.3, 2.4, 3.5
output = 30 2 4
_______________________________

input = 30.9, 2.4, 3.9
output = 31 2 4
_______________________________

Approach: Recursion

Try out each possibility, ceil and floor for each price in the given array to get to target and keep track of rounding difference for every possibility and pick the minimum one. See the code for better understanding.

Time Complexity: O(2n)

Output:

Prices: [30.9, 2.4, 3.9]
Rounded Prices: 31 2 4

Better Solution: Sorting

  1. Calculate Ceil and Floor for each given price. 
  2. Get the sum of all prices and calculate the target price = round (sum of all prices).
  3. Calculate floorSum with all floor prices.
  4. Get difference d = target - floorSum. (this is the value we need to achieve by picking ceil values on prices)
  5. Create an array PriceWithDiff with each price with Ceil, floor, and difference of price with ceil value.
  6. Sort the array on the difference of price with ceil value. ( so that we can pick the ceil values with less rounding margin)
  7. Pick the first d ceil values from PriceWithDiff and pick the floor from the rest of the array. This will be our final result.

Time Complexity: O(NLogN),

Space Complexity: O(N)

Output:

Prices: [30.9, 2.4, 3.9]
Rounded Prices: [4, 31, 2]

Related Problems: