- Practice
- Algorithms
- Greedy
- Greedy Florist
- Discussions

# Greedy Florist

# Greedy Florist

cgnicholls + 5 comments I think this problem is poorly worded. It should say that as a group you have to buy one flower of each type. As stated, it could mean you simply want to buy N flowers; in this interpretation, you would only ever buy the cheapest type of flower. The example shows that it is the other interpretation that is correct, but the problem statement is ambiguous.

david_guijarro + 1 comment +1, totally correct it is really poorly written...

iainws + 1 comment Thanks, good problem. Hard to understand at first.

edrouwendaal + 0 comments also starting programme for C# does not have initial size of array

FaxMachin3 + 6 comments # C# Code:

**O(n + nLogn)**int n = c.Length; int minCost = 0; int tempCount = 0; int previousPurchases = 0; Array.Sort(c); if(k >= n){ for(int i = 0; i < n; i++) minCost += c[i]; } else{ for(int i = n - 1; i >= 0; i--){ if(tempCount == k){ tempCount = 0; previousPurchases++; } minCost += (previousPurchases + 1) * c[i]; tempCount++; } } return minCost;

2017uee1085 + 1 comment you can keep a track of purchases of individual customers in an array by initialising default values with zero and access them by %k in iteration of cost loop.

sigmasys + 0 comments no need. if only c[i]+n<=c[i+1], continue by c[i]. unitle the whole c list done.

99abhii + 0 comments [deleted]99abhii + 0 comments [deleted]abieleck + 0 comments Instead of keeping track of the number of purchases, one can just multiply each price by j / k + 1, where j / k is in integer arithmetic. j is the purchase number, starting from 0 for the first purchase.

aburduk + 0 comments What the others said, except you need to sort descending and iterate forwards in order for it to work.

nikolicav + 0 comments C# solution with Dictionary, Pass 100%.

public int getMinimumCost(int k, int[] c) { Array.Sort(c); IDictionary<int, int> dict = new Dictionary<int, int>(); int sum = 0; // first sell most expensive flower to each person for (int i = c.Length - 1; i >= c.Length - k; i--) sum += c[i]; // current person int current = 0; for (int i = c.Length - k; i > 0; i--) { // counter how many flowers every person // alredy bought if (dict.ContainsKey(current)) dict[current] += 1; else dict.Add(current, 1); // calculate sum with current price and count of // flower current person already bought sum += (dict[current] + 1) * c[i - 1]; // move to next person current++; // if all persons bought same number of flowers // reset current person to first if (current == k) current = 0; } return sum; }

muthangyamusyoka + 0 comments Yap, also finding it very ambigous.

gurunars + 0 comments Yes. It is very badly written.

ailhahc + 4 comments The problem statement is wrong. In problem statement it's written More precisely, if a customer has already bought x flowers, he should pay (x+1)/ci dollars to buy flower number i.

It should be he should pay (x+1)*ci

sagioto + 0 comments Why is this not being corrected?

rgevorky + 0 comments The problem is also just written poorly, like MANY others on this website. The author writes of flower number i, where he/she presumably means flower type i, since we also have N, the number of flowers we want to buy. The problem further does not state the implicit assumption that the group can buy any N flowers (type doesn't matter).

vikasgandhi003 + 0 comments YEAH YEAH I AGREE WITH THAT

andepzaifggg + 0 comments haha

phillm6 + 4 comments Just to clarify, as some people seem to be having a few problems. If Anne and Bob go to buy flowers [1,2,7,9,100], then the minimum price is 130. Why?

Assume only one person buys the flowers in the given order. So, she pays (1)1+(2)2+(3)7+(4)9+(5)100 = 562. From this we can see that order matters; for example, if she buys them in the opposite order, we get (1)100+(2)9+(3)7+(4)2+(5)1 = 152! Even without a second person, we can see that an opportunistic order drastically improves the price.

So, hopefully without giving the problem away, what we would want to do is assign the flowers to Anne and Bob in such a way not only to reduce the total number each person purchases [so that no person will buy an ith flower larger than is necessary (so that their ith multiplyer will be no larger than is necessary for any given flower)], but to assign the order they buy their flowers responsibly as well.

Note: the oder of the*people*does not affect the price, only the order of flowers purchased by each person.dalmia_anmol + 1 comment Hello. Could you show the distribution of purchases that results into 130 cost?

phillm6 + 4 comments A purchases (1)100 + (2)7 + (3)1 = 100 + 14 + 3 = 117

B purchases (1)9 + (2)2 = 9 + 4 = 13

P(A) + P(B) = 130 (this is one possible distribution)

Remember that we have

*two*people, so we can repeat coefficients up to*two*times each. We can therefore construct any permutation of the list [1,1,2,2,3] to multiply elementwise with the prices. It's simply a matter of choosing the most advantageous order to purchase.dalmia_anmol + 1 comment Ok, thanks. But I am unable to understand then how Greedy comes into the picture.

phillm6 + 2 comments Well, what are we doing, and is what we're doing greedy?

Because the coefficients are constantly increasing (at a rate of 1 per k purchases), we purchase the most expensive flowers first in order to minimize cost, rotating people to hold coefficients down as long as possible.

Assuming this rotation of customers, the algorithm

*optimizeses at each step*by choosing to purchase the most expensive remaining flower.Recall that this is the definition of a greedy algorithm.

dalmia_anmol + 0 comments Kudos. Apologies for not observing the rotation part. Thanks for the help.

beezerbtt + 0 comments Thats the answer basically.

sheelnidhi + 1 comment Hi,I am unable to understand how the distribution works?If there is two friends and they have to buy total 3 flowers then who will buy two.Someone can buy only single flower.

phillm6 + 3 comments It doesn't really matter.

Call the flowers [3,2,1]. A or B takes the most expensive flower, say A for argument. A pays (1)3 = 3. Now the next most expensive flower could be purchased by A or B. If A purchases it, it will cost (2)2 = 4, but if B does it will cost (1)2 = 2, so B should purchase.Now we need to buy the 1 flower, and both A and B have a coefficient of 2 now, so it doesn't matter who does. (You don't even have to keep track of people to solve the problem!)

dont_know_me + 0 comments thank you so much.. I got the solution only after reading this.

lalithnani + 0 comments thanks

da182 + 0 comments Thanks for such a concise explanation!

Akshita_Sood + 0 comments thanks a lot.this was helpful.

simonsatoshi + 0 comments Thank you! 15 minutes to understand the question. 2 minutes to code it.

shshnk28 + 0 comments Now this is a nice description. It made understanding the problem easier.

rwan7727 + 1 comment `int n; int k; cin >> n >> k; vector <int> c(n); for(int i=0;i<n;i++) cin >> c[i]; vector <int> p(k); // stores how many times a person has bought flowers int pIndex=0; int minCost=0; sort(c.begin(),c.end()); // rotate people to buy from the costliest to the cheapest flowers for (int i=c.size()-1;i>=0;i--) { minCost+=(p[pIndex]+1)*c[i]; p[pIndex]++; // goto next guy pIndex++; if (pIndex>=k) pIndex=0; } cout << minCost << endl;`

jnordwick + 5 comments Not even that complex:

int main() { int n, k; cin >> n >> k; vector<int> v(n); for(int i = 0; i < n; ++i) cin >> v[i]; sort(v.begin(), v.end()); reverse(v.begin(), v.end()); int tot = 0; for(int i = 0; i < n; ++i) { tot += ((i / k) + 1) * v[i]; } cout << tot << endl; return 0; }

fynx_gloire + 1 comment Hello can you explain your code for the Greedy Florist here: m = floor(i/K)+1;

Why are you dividing the i by number of customers?

veden_joshua + 0 comments they divide i by k in order to figure out the number of flowers the person has purchased before purchasing the ith flower. For example, if there are 3 friends (k = 3) purchasing from 5 flowers (n = 5), then on the 3rd iteration (i = 2) this person will be purchasing their first flower (2/3 + 1 = 1),. This can be thought of as the 3rd friend purchasing their first flower. On the fourth iteration (i = 3), this person will be purchasing their second flower (3/3 + 1 = 2). This can be thought of as the 1st friend purchasing their second flower. Hope this helps.

rams_m02 + 0 comments so simple and elgant. thanks!

satyamskillz + 0 comments `def getMinimumCost(k, c): c.sort(reverse=True) l=len(c) t=0 for i in range(l): t=t+(int(i/k)+1)*c[i] return t`

This can become more simple in python

rafat_joy0707 + 0 comments gives wrong answer .

soheshdoshi + 0 comments Grt Man

Aakash8250 + 0 comments its simple brother, first buy=100(1)+9(1) second buy=7(2)+2(2) third buy=1(2) add all = 130

sheldonrong + 7 comments def getMinimumCost(n, k, c): cost = 0 c = sorted(c, reverse=True) for i in range(0, n): cost += (i // k + 1) * c[i] return cost

metazilla + 1 comment Nice, here's a one-liner based off your solution:

def getMinimumCost(k, c): return sum([cost * ((i // k) + 1) for i, cost in enumerate(sorted(c, reverse=True))])

it_henrik + 0 comments I would recommend to skip the listcomprehension and go for a generator expression instead to save some time and memory:

def getMinimumCost(k, c): return sum((v * (i // k + 1) for i, v in enumerate(sorted(c, reverse=True))))

or for readability:

def getMinimumCost(k, c): c.sort(reverse=True) return sum((v * (i // k + 1) for i, v in enumerate(c)))

angelopolotto + 0 comments Less pythonic but my solution work too:

`def getMinimumCost(k, c): c_len = len(c) total = sum(c) if k >= c_len: return total c_s = sorted(c, reverse=True) total = sum(c_s[:k]) c_diff = c_s[k:] i = 1 j = 1 for c_i in c_diff: total += c_i * (1 + i) if j < k: j += 1 else: i += 1 j = 1 return total`

hacker_jkjffjha + 0 comments javascript 1-liner implementation:

function getMinimumCost(k, c) { return c.sort((a, b) => b - a).reduce((acc, cost, index) => acc + (parseInt(index / k) + 1) * cost, 0) }

pamuditha_i + 0 comments Nice!

switchoffking + 0 comments [deleted]switchoffking + 0 comments [deleted]josiahtpz + 0 comments What's the reason behind i//k ? How does it link to number of previously bought flowers

renolu + 1 comment Simple Java approach by buying the flowers backward from the most expensive to least expensive:

import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner s = new Scanner(System.in); int n = s.nextInt(); int k = s.nextInt(); int[] flowers = new int[n]; for(int i=0;i<n;i++){ flowers[i]=s.nextInt(); } System.out.println(CalculateMinPrice(flowers,k)); } static int CalculateMinPrice(int[] flowers,int k){ //sort all flower prices in ascending order Arrays.sort(flowers); int i = flowers.length-1; int bought = 0; int total=0; //start backwards from the most expensive flower, stop when there is no more flowers left while(i>=0){ //Calculate total //increment bought by 1 when everyone in the group has bought equal number of flowers for(int j=0;j<k && i>=0;j++){ total+=(1+bought)*flowers[i]; i--; } bought++; } return total; } }

ray10mathew + 1 comment I feel so stupid looking at your solution. Took me ages to try and come up with a logic.

saisuneela24 + 0 comments hoo really

maicaho + 4 comments /* Sample program illustrating input/output */ #include<iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; int main(void){ int N, K; cin >> N >> K; vector<int> C(N); for(int i = 0; i < N; i++){ cin >> C[i]; } /* * The way I understand it, the "greedy" applies to the florist, not to the algorithm used to * solve the challenge. * My solution presented here passed. * The algorithm to minimize cost for your group to purchase N flowers: * 1. Buy the first K most expensive flowers at their lowest prices each (which is 1 X c_i.) * 2. Buy the second K most expensive flowers at 2 X c_i each * 3. ... * 4. Buy the last (i.e. the m) K most expensive flowers at m X c_i each. */ sort(C.begin(), C.end(), greater<int>()); int result = 0, m; for (int i=0; i<N; i++) { m = floor(i/K)+1; result += C[i] * m; } cout << result << std::endl; return 0; }

anh_duc + 0 comments Very nice solution ! Thank you

levpolka + 0 comments `public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); int[] A = new int[n]; for (int i = 0; i < n; i++) { A[i] = in.nextInt(); } Arrays.sort(A); int sum = 0; for (int i = n - 1; i >= 0; i--) { sum += A[i] * ((n - i - 1) / k + 1); } System.out.println(sum); }`

sasuke29 + 0 comments int getMinimumCost(int k, vector<int> c) { sort(c.begin(),c.end(),greater<int>()); int i=0, j=0, ans=0; while(i<c.size()) { while(k-- && i<c.size()) { ans += (j+1)*c[i]; i++; } j++; } return ans; }

Can you tell me what is wrong with my approach. 5 test cases are failing.

fynx_gloire + 0 comments Hello can you explain your code for the Greedy Florist here: m = floor(i/K)+1;

Why are you dividing the i by number of customers?

arun0102 + 2 comments Java solution. The problem should be under easy section(I may be wrong).

static int getMinimumCost(int k, int[] c) { int cost = 0; Arrays.sort(c); int multiplier = 0; int count = k; for (int i = c.length - 1; i >= 0; i--) { cost += (multiplier + 1) * c[i]; count--; if (0 == count) { multiplier++; count = k; } } return cost; }

ocv808 + 0 comments Came up with something similar agree it seemed very easy. I calculated my multiplier differently.

static int getMinimumCost(int k, int[] c) { Arrays.sort(c); int total = 0; for (int i = c.length - 1; i >= 0; --i) { int timesBought = ((c.length - 1) - i) / k; int price = c[i] * (timesBought + 1); total += price; } return total; }

woldegebrielkeb1 + 2 comments yup this problem was super easy.

static int getMinimumCost(int k, int[] c) { Arrays.sort(c); int counter = 0; int pre = 0; int minCost = 0; for(int i=c.length-1; i>=0; i--) { while(i>=0&&counter<k) { minCost += c[i]*(pre+1); counter++; i--; } i++; counter = 0; pre++; } return minCost; }

alvi_tariq + 0 comments I feel their explanation is wrong and they come up with the wrong answer for this case: n = 3. c={2,5,6}. k=2

If the first person buys 3rd and first flower, they pay 6 + 3=9 The second person buys the second flower at 5. The total is 9+5=14.

Which is less than their answer of 15 because they did it in exactly the reverse order.

tarik_ourida + 0 comments [deleted]

chandra82p + 0 comments Problem statement was not written properly! Lots of problems in Hackerrank are not properly stated.

SARFRAJ3333 + 0 comments def getMinimumCost(k, c): times=len(c)/k c.sort(reverse=True) sum=0 for i in range(len(c)): sum+=c[i]*((i//k)+1) return sum

Sort 327 Discussions, By:

Please Login in order to post a comment