FastPrep
Problem · Greedy

Minimum Price With Discount Coupons

● MediumAgodaCONTRACTOA

A store offers n items, where price[i] is the original price of the i-th item. A customer has m discount coupons.

If x coupons are applied to the i-th item, its price is reduced to floor(price[i] / 2^x).

Return the minimum total cost to purchase all items by optimally allocating at most m coupons.

Examples
01 · Example 1
price = [2,4]
m = 2
return = 3

Buy the first item for 2. Apply both coupons to the second item, reducing its price to floor(4 / 2^2) = 1. The minimum total cost is 2 + 1 = 3.

Constraints
  • 1 <= price.length
  • 0 <= m
  • price[i] >= 0
More Agoda problems
drafts saved locally
public int findMinimumPrice(int[] price, int m) {
  // write your code here
}
price[2,4]
m2
expected3
sign in to submit