Interviewstreet Challenge: Flowers

Problem
https://www.interviewstreet.com/challenges/dashboard/#problem/4fd05444acc45

You and your K-1 friends want to buy N flowers. Flower number i has host c_i. Unfortunately the seller does not like a customer to buy a lot of flowers, so he tries to change the price of flowers for customer who had bought flowers before. More precisely if a customer has already bought x flowers, he should pay (x+1)*c_i dollars to buy flower number i.
You and your K-1 firends want to buy all N flowers in such a way that you spend the as few money as possible.

Input:

The first line of input contains two integers N and K.
next line contains N positive integers c₁,c₂,...,c_N respectively.

Output:

Print the minimum amount of money you (and your friends) have to pay in order to buy all n flowers.

Sample onput :

3 3
2 5 6

Sample output :

13

Explanation :
In the example each of you and your friends should buy one flower. in this case you have to pay 13 dollars.

Constraint :

1 <= N, K  <= 100
Each c_i is not more than 1000,000

Analysis

All Java Solutions on the InterviewStreet needs to run in 5 seconds with 256 MB maximum RAM available. So that means our solution can never be "Brute-Force" or O(n^2). Same applies to the space complexity.

The task is to find out the total cost such that it is minimum. And we can get minimum cost only if the cost (x+1)*ci is minimum. That means X should be minimum and ci should also be minimum. So this indicates that each person should buy flowers uniformly. We cannot have person A buying 3 flowers and person B buying only 1. So we should use round-robin algorithm here - each person buy one flower at a time. And to make ci minimum means, we need to buy low cost flowers later. That means start buying high cost flowers and then move to low cost ones. 

So we arrive at a solution - Sort the costs and use round-robin

For instance if the costs are- 9, 6, 8, 7. And lets say there are 3 people who want to buy. Then it means 1 person has to buy 2 flowers and the other 2 buy one each. And also the person who buys 2 flowers, should buy the flower with cost 6 (minimum cost) as the 2nd flower. So that gives us-

Person A = 9, 6

Person B = 8

Person C = 7

Solution