Flowers Challenge on HackerRank

Question

I worked through the Flowers challenge on hackerrank.com and would like to get feedback on solution and algorithm implementation. It was suggested by hackerrank to review greedy algorithm to solve this challenge. As far as I understand this is an implementation of greedy algorithm.

You and your \$K−1\$ friends want to buy \$N\$ flowers. Flower number \$i\$ has cost \$c_i\$. Unfortunately the seller does not want just one customer to buy a lot of flowers, so he tries to change the price of flowers for customers who have already bought some flowers. More precisely, if a customer has already bought \$x\$ flowers, he should pay \$(x+1) \times c_i\$ dollars to buy flower number \$i\$.

You and your \$K−1\$ friends want to buy all \$N\$ flowers in such a way that you spend the least amount of money. You can buy the flowers in any order.

Input:

The first line of input contains two integers \$N\$ and \$K\$ (\$K≤N\$). The next line contains \$N\$ space separated positive integers \$c_1,c_2,\dots,c_N\$.

Output:

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

import java.io.*;
import java.util.*;

public class Flowers {

    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 sc = new Scanner(System.in);
        ArrayList <Integer> flowerPriceList = new ArrayList<Integer>();
        int numFlowers = sc.nextInt();
        int numFriends = sc.nextInt();
        for(int i = 0; i<numFlowers;i++){
            flowerPriceList.add(sc.nextInt());
        }
        // Sort the ArrayList in reverse order to start bying flowers from most expensive
        Collections.sort(flowerPriceList,Collections.reverseOrder());
        int flowersBought = 0;
        int friendNum = 0;
        int total = 0;
        for(int price:flowerPriceList){
            //itterate throught all the flower prices and calculate the total
            total +=(flowersBought+1)*price;
            friendNum++;
            if(friendNum == numFriends){
                //if all friends bought flowers reset the friend counter and restart the cycle
                friendNum = 0;
                flowersBought++;
            }
        }
        System.out.println(total);
    }
}

Answer 1

Class name and general comments

Your class is named Flowers but there is a comment here that says:

/* (...) Your class should be named Solution. */

Although I think that Flowers is a much better name, personally.

Generally, I understood your code better than the assignment description, so well done there.

Array instead of ArrayList

Instead of using an ArrayList <Integer>, that by the way would be better to declare as List<Integer> (use interface for declaration, implementation for initialization), you could use an int[] instead, as you know the exact size of the list. There's no need to do any dynamical resizing of the list, so a int[] would be just fine.

Small spacing nitpick

A little nitpick would be to use a bit more spacing, I am a bit allergic to lines like this:

for(int i = 0; i<numFlowers;i++){

better would be:

for (int i = 0; i < numFlowers; i++) {

And also:

total +=(flowersBought+1)*price;

becomes:

total += (flowersBought + 1) * price;

Closing statement

Again, your code was very readable and your approach is good, and indeed it is a greedy algorithm

As said on Hackerrank:

A greedy algorithm is an algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

This is indeed what your code does. It always picks a way to buy the flower in the cheapest way.

Answer 2

Comment by @spyr03:

you can replace the check friendNum == numFriends with friendNum = (friendNum + 1) % numFriends