HackerRank Greedy Florist

This is the solution for the HackerRank Greedy Florist problem, in python. This is a problem in the Interview Preparation Kit > Greedy Algorithms and is considered medium.

The problem is as follows:

• The greedy florist wants to maximize his price
• He has a formula to the price: (n + 1) * original price
• n is the number of flowers previously purchased

So, if you buy one flower, it will be the original price. If you buy a second flower, the price is 2 * original price.

I think that the problem never left clear that the expensive flowers must be purchased first, but that’s in the answer.

Solution

The first problem we must solve is to put the array in a reverse price order.

    <span>c</span><span>.</span><span>sort</span><span>()</span>
    <span>c</span><span>.</span><span>reverse</span><span>()</span>
    <span>c</span><span>.</span><span>sort</span><span>()</span>
    <span>c</span><span>.</span><span>reverse</span><span>()</span>
    c.sort()
    c.reverse()

Enter fullscreen mode Exit fullscreen mode

So we can traverse it and buy the flowers. For each item, we must find:

• n
• current cost

We can find n by integer (or floor) dividing the array position with the number of friends k

    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>len</span><span>(</span><span>c</span><span>)):</span>
        <span>n</span> <span>=</span> <span>i</span> <span>//</span> <span>k</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>len</span><span>(</span><span>c</span><span>)):</span>
        <span>n</span> <span>=</span> <span>i</span> <span>//</span> <span>k</span>
    for i in range(len(c)):
        n = i // k

Enter fullscreen mode Exit fullscreen mode

So, the first round of purchases will have n = 0, the second, n = 1, and so on.

The cost is straight to the formula:

        <span>flower_cost</span> <span>=</span> <span>c</span><span>[</span><span>i</span><span>]</span>
        <span>cost</span> <span>=</span> <span>(</span><span>n</span> <span>+</span> <span>1</span><span>)</span> <span>*</span> <span>flower_cost</span>
        <span>flower_cost</span> <span>=</span> <span>c</span><span>[</span><span>i</span><span>]</span>
        <span>cost</span> <span>=</span> <span>(</span><span>n</span> <span>+</span> <span>1</span><span>)</span> <span>*</span> <span>flower_cost</span>
        flower_cost = c[i]
        cost = (n + 1) * flower_cost

Enter fullscreen mode Exit fullscreen mode

And that’s it. The complete solution is as follow:

<span>def</span> <span>getMinimumCost</span><span>(</span><span>k</span><span>,</span> <span>c</span><span>):</span>
    <span>total</span> <span>=</span> <span>0</span>
    <span>c</span><span>.</span><span>sort</span><span>()</span>
    <span>c</span><span>.</span><span>reverse</span><span>()</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>len</span><span>(</span><span>c</span><span>)):</span>
        <span>n</span> <span>=</span> <span>i</span><span>//</span><span>k</span>
        <span>flower_cost</span> <span>=</span> <span>c</span><span>[</span><span>i</span><span>]</span>
        <span>cost</span> <span>=</span> <span>(</span><span>n</span> <span>+</span> <span>1</span><span>)</span> <span>*</span> <span>flower_cost</span>
        <span>total</span> <span>+=</span> <span>cost</span>
    <span>return</span> <span>total</span>
<span>def</span> <span>getMinimumCost</span><span>(</span><span>k</span><span>,</span> <span>c</span><span>):</span>
    <span>total</span> <span>=</span> <span>0</span>
    <span>c</span><span>.</span><span>sort</span><span>()</span>
    <span>c</span><span>.</span><span>reverse</span><span>()</span>

    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>len</span><span>(</span><span>c</span><span>)):</span>
        <span>n</span> <span>=</span> <span>i</span><span>//</span><span>k</span>
        <span>flower_cost</span> <span>=</span> <span>c</span><span>[</span><span>i</span><span>]</span>
        <span>cost</span> <span>=</span> <span>(</span><span>n</span> <span>+</span> <span>1</span><span>)</span> <span>*</span> <span>flower_cost</span>
        <span>total</span> <span>+=</span> <span>cost</span>
    <span>return</span> <span>total</span>
def getMinimumCost(k, c):
    total = 0
    c.sort()
    c.reverse()

    for i in range(len(c)):
        n = i//k
        flower_cost = c[i]
        cost = (n + 1) * flower_cost
        total += cost
    return total

Enter fullscreen mode Exit fullscreen mode

原文链接：HackerRank Greedy Florist