FastPrep
Problem · Heap

Items Purchase (For Java Backend Engineer)

Learn this problem
● MediumPaypalOA

Problem statement

n items where the price of the ith item is price[i]. A frequent customer has m discount coupons. If x discount coupons are used on the ith item, its price is reduced to the integer floor(price(i) / 2^x), e.g. floor(3/2^1) = floor(1.5) = 1. Find the minimum amount needed to purchase all the items of the shop using at most m coupons.

Function

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

Complete the function findMinimumPrice in the editor below.

findMinimumPrice has the following parameters:

  1. int price[n]: the original prices of the items
  2. int m: the number of discount coupons

Returns

int: the minimum amount needed to purchase all items

Examples

Example 1

price = [2, 4]m = 2return = 3

The optimum solution:

  • Purchase item 1 for 2.
  • Use 2 coupons on item 2, so the discounted price is 4/2^2 = 4 / 4 = 1.
The amount required = 2 + 1 = 3.

Constraints

  • 1 <= n <= 10^5
  • 0 <= m <= 10^9
  • 1 <= price[i] <= 10^9

    • More Paypal problems

    drafts saved locally
    public int findMinimumPrice(int[] price, int m) {
  // write your code here
}
    price[2, 4]
    m2
    expected3
    checking account