FastPrep
Problem · Greedy

Minimum Price With Discount Coupons

Learn this problem
● MediumAGAgodaCONTRACTOA

Problem statement

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.

Function

findMinimumPrice(price: int[], m: int) → int

Examples

Example 1

price = [2,4]m = 2return = 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
checking account