← All questions
Coding

Buy Flowers

Asked atAmazon
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

The problem

There is a huge garden in the city. The Garden contains n numbers of flowers. James has arrived in that city to buy exactly k flowers. He then went to the owner of this garden to discuss the prices of flowers. The owner of the garden provides James with an array ‘cost’ of n numbers which denotes the prices of the flower, the price of ith flower is cost[i].

Since today is the Birthday of Garden Owner , so he has provides a discount which is given by 2D array ‘discount’, where 1st column represents x and second column represent y. It represents that on buying any x flowers from the n flowers, the yth cheapest flower from that x flowers is free.

Let's say we have flowers with cost [1, 1, 3, 4] then for x=3 and y=2, if we pick any three flowers say [1, 3, 4], then second cheapest flower that is flower with cost 3 is free and you have to pay only first and third flower i.e. 1+4=5. Also other way is, if you pick [1, 1, 3] then the second cheapest flower that is flower with cost '1' will be free and you will pay only for the cost of first and third flower i.e. 1+3=4.

Since James has other plans as well, he wants to save money. So he has asked you to buy exactly k flowers with the minimum cost possible.

Input : n = 5, m = 2, k = 4, cost = [2, 3, 1, 5, 4], discount = [ [2, 1], [3, 2] ] Output : 6 Explanation : First James will buy 2 flowers of cost 1 and 2 and using 1st discount he will get both flowers in just 2 Rs. Then James will buy 2 more flowers of cost 3 and 4 and using 1st discount he will get both flowers in just 4 Rs. So total cost = 2 + 4 = 6.

Input : n = 5, m = 2, k = 3, cost = [100, 100, 100, 100, 100], discount = [ [2, 1], [3, 3] ] Output : 200 Explanation : First James will buy 2 flowers of cost 100 and 100 and using 1st discount he will get both flowers in just 100 Rs. Then james will buy 3rd flower of cost 100 and now there is no discount on buying 1 flower, so he will get 3rd flower in 100Rs. So total cost = 100 + 100 = 6.

Input : n = 6, m = 4, k = 4, cost = [9, 3, 7, 2, 10, 1], discount = [ [2, 2], [3, 3], [4, 4], [5, 5] ]

  • 1 <= m <= n <= 2*105
  • 0 <= k <= min(2000,n)
  • 0 <= cost[i] <= 109
  • 1 <= y <= x <= n

cpp

class Solution{
    public:
        long long int buyFlowers(vector<int> &cost, vector<vector<int>> &discount, int k){
            //your code goes here
        }
};

java

class Solution {
    public long buyFlowers(Integer[] cost, Integer[][] discount, int k) {
        //your code goes here
    }
}

python

class Solution:
    def buyFlowers(self, cost, discount, k):
        #your code goes here

javascript

class Solution {
    buyFlowers(cost, discount, k) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public long buyFlowers(int[] cost, int[][] discount, int k)
    {
        // your code goes here
    }
}

go

func buyFlowers(cost []int, discount [][]int, k int) int64 {
        //your code goes here
    }
Stuck? Show a way to structure it+
  1. 01Sort flower costs ascending and consider only the first k.
  2. 02For each group size x, derive the payable cost after its y-th cheapest flower is free.
  3. 03Use DP over how many flowers have been bought.
  4. 04Minimize over taking a valid discounted group or buying one flower normally.

Reference answer

Then expect these follow-ups

  • How would you optimize when there are many duplicate discount sizes?

    Tests: transition pruning

  • Why is sorting globally safe before grouping?

    Tests: exchange argument

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with EnzoSign up free

Next question