Hackerrank - Greedy Florist Solution

Hackerrank - Greedy Florist Solution

A group of friends want to buy a bouquet of flowers. The florist wants to maximize his number of new customers and the money he makes. To do this, he decides he'll multiply the price of each flower by the number of that customer's previously purchased flowers plus . The first flower will be original price, , the next will be  and so on.

Given the size of the group of friends, the number of flowers they want to purchase and the original prices of the flowers, determine the minimum cost to purchase all of the flowers.

For example, if there are  friends that want to buy  flowers that cost  each will buy one of the flowers priced  at the original price. Having each purchased  flower, the first flower in the list, , will now cost . The total cost will be .

Function Description

Complete the getMinimumCost function in the editor below. It should return the minimum cost to purchase all of the flowers.

getMinimumCost has the following parameter(s):

  • c: an array of integers representing the original price of each flower
  • k: an integer, the number of friends

Input Format

The first line contains two space-separated integers  and , the number of flowers and the number of friends.
The second line contains  space-separated positive integers , the original price of each flower.

Constraints

Output Format

Print the minimum cost to buy all  flowers.

Sample Input 0

3 3
2 5 6

Sample Output 0

13

Explanation 0

There are  flowers with costs  and  people in the group. If each person buys one flower, the total cost of prices paid is  dollars. Thus, we print  as our answer.

Sample Input 1

3 2
2 5 6

Sample Output 1

15

Explanation 1

There are  flowers with costs  and  people in the group. We can minimize the total purchase cost like so:

  1. The first person purchases  flowers in order of decreasing price; this means they buy the more expensive flower () first at price  dollars and the less expensive flower () second at price  dollars.
  2. The second person buys the most expensive flower at price  dollars.

We then print the sum of these purchases, which is , as our answer.

Sample Input 2

5 3
1 3 5 7 9

Sample Output 2

29

Explanation 2

The friends buy flowers for ,  and ,  and  for a cost of .

Solution in Python

def getMinimumCost(k, c):
    return sum((sum(c[i:i+k])*(i//k+1)) for i in range(0,len(c),k))

n,k = map(int,input().split())
c = sorted(map(int,input().split()),reverse=True)
print(getMinimumCost(k, c))

Subscribe to The Poor Coder | Algorithm Solutions

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
[email protected]
Subscribe