Greedy florist Solution

This is one of the medium difficulty problems in the Greedy algorithms section of Hackerrank’s interview preparation kit problem set. Link here.

The problem states that k friends want to purchase all flowers available in a shop. However the florist keeps track of each person’s purchases to adjust the price of the next flower they purchase. The price of a flower is given by
P(flower_price, prev_purch) = flower_price*(1+prev_purch) . The friends want to purchase all the flowers collectively and minimize the cost.

Solution

To solve this problem what we need to do is to sort the flower base prices by increasing or decreasing order. Whichever you like better. I like to iterate arrays bottom up so i chose decreasing price. Now we need an array to keep track of the purchases of the friends initialized to 0s. We can get the minimum cost by choosing the (i%k)th person to buy the ith most expensive flower and add the adjusted price to our solution. After this we add one to the (i%k)th person’s purchases so the next time he buys a flower, the florist charges the adjusted price.

Code

Link to solution on github

static bool sortFn (int i, int j) { return (i>j); }
static int purchases[100];
int getMinimumCost(int k, vector<int> c) {
    
    int cost = 0;
    int n = c.size();
    sort(c.begin(), c.end(), sortFn);
    
    for(int i = 0; i < n; i++){     
        cost+=c[i]*(purchases[i%k]+1);
        purchases[i%k]++;
    }
    
    return cost;
}