Hackerrank Cut the sticks Solution I have started learning Java recently and I solved the following problem on Hackerrank.

The challenge is to :


  You are given NN sticks, where the length of each stick is a positive integer. A cut operation is performed on the sticks such that all of them are reduced by the length of the smallest stick.
  
  Suppose we have six sticks of the following lengths:
  5 4 4 2 2 8
  
  Then, in one cut operation we make a cut of length 2 from each of the six >sticks. For the next cut operation four sticks are left (of non-zero length), >whose lengths are the following: 
  3 2 2 6
  
  The above step is repeated until no sticks are left.
  
  Given the length of NN sticks, print the number of sticks that are left before each subsequent cut operations.
  
  Note: For each cut operation, you have to recalcuate the length of smallest sticks (excluding zero-length sticks).
  
  Input Format 
  The first line contains a single integer NN. 
  The next line contains NN integers: a0, a1,...aN-1 separated by space, where ai represents the length of ith stick.
  
  Output Format 
  For each operation, print the number of sticks that are cut, on separate lines.


Sample Input :

6
5 4 4 2 2 8


Sample Output:

6
4
2
1


I am trying to get better at writing good code for my solutions. Please give me your suggestions.

 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Scanner;


 public class CutSticks {
 public static void main(String[] args) {

    Scanner keyboard = new Scanner(System.in);

    int size = keyboard.nextInt(); // get total number of sticks

    ArrayList&lt;Integer&gt; list = new ArrayList&lt;Integer&gt;(size);
    for(int i=0;i&lt;size;i++)
    {
        int values = keyboard.nextInt();
        list.add(values);
    }
     list.removeAll(Collections.singleton(0));// remove all zeroes if present
     Collections.sort(list); // sort in ascending order
        while(list.size()&gt;0)
        {
            int smallest = list.get(0);  // get the smallest element
            for(int i =0 ;i &lt; list.size();i++)
            {

                list.set(i, list.get(i) - smallest);
            }
            //System.out.println(list);
            System.out.println(list.size());
            list.removeAll(Collections.singleton(0)); // remove the elements which are zero after cutting the sticks
            //System.out.println(list);
        }



   }

  }
Improving the algorithm

Realize that you don't actually need to remove elements from a collection. You can just count how many sticks would disappear in each step.

Take for example this sorted list of sticks:


1 1 1 2 2 3 3 3 3 3 4 5 5 5



At each cutting step, the shortest sticks disappear:


1 1 1 2 2 3 3 3 3 3 4 5 5 5
^^^^^
3 will disappear

      2 2 3 3 3 3 3 4 5 5 5
      ^^^
      2 will disappear

          3 3 3 3 3 4 5 5 5
          ^^^^^^^^^
          5 will disappear



And so on. You can just count the number of sticks that will disappear, and figure out from that how many will remain.

Use interface types in declarations

Instead of this:


ArrayList&lt;Integer&gt; list = new ArrayList&lt;Integer&gt;(size);



It's recommended to declare variables with their interface types:

List&lt;Integer&gt; list = new ArrayList&lt;Integer&gt;(size);


Style

This is way too compact writing style:


for(int i=0;i&lt;size;i++)



It's much more readable this way, by putting spaces around operators:

for (int i = 0; i &lt; size; i++)


Checking an empty list

Instead of this:


    while(list.size()&gt;0)



A more idiomatic way to write:

    while(!list.isEmpty())


Suggested implementation

Putting the above tips together:

public static void main(String[] args) {
    List&lt;Integer&gt; sticks = readSticksFromStdin();
    Collections.sort(sticks);

    int pos = 0;
    int remaining = sticks.size();
    while (0 &lt; remaining) {
        System.out.println(remaining);
        int count = countEqualFrom(sticks, pos);
        pos += count;
        remaining -= count;
    }
}

private static int countEqualFrom(List&lt;Integer&gt; sticks, int from) {
    int value = sticks.get(from);
    for (int i = 1; from + i &lt; sticks.size(); ++i) {
        if (value != sticks.get(from + i)) {
            return i;
        }
    }
    return sticks.size() - from;
}

private static List&lt;Integer&gt; readSticksFromStdin() {
    Scanner scanner = new Scanner(System.in);
    int num = scanner.nextInt();
    List&lt;Integer&gt; sticks = new ArrayList&lt;&gt;(num);
    for (int i = 0; i &lt; num; ++i) {
        sticks.add(scanner.nextInt());
    }
    return sticks;
}