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 list = new ArrayList(size);
for(int i=0;i0)
{
int smallest = list.get(0); // get the smallest element
for(int i =0 ;i < list.size();i++)
{

list.set(i, list.get(i) - smallest);
}
//System.out.println(list);
System.out.println(list.size());
list.removeAll(C

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 list = new ArrayList(size);

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

List list = new ArrayList(size);

Style

This is way too compact writing style:

for(int i=0;i<size;i++)

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

for (int i = 0; i < size; i++)

Checking an empty list

Instead of this:

while(list.size()>0)

A more idiomatic way to write:

while(!list.isEmpty())

Suggested implementation

Putting the above tips together:

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

    int pos = 0;
    int remaining = sticks.size();
    while (0  sticks, int from) {
    int value = sticks.get(from);
    for (int i = 1; from + i  readSticksFromStdin() {
    Scanner scanner = new Scanner(System.in);
    int num = scanner.nextInt();
    List sticks = new ArrayList<>(num);
    for (int i = 0; i < num; ++i) {
        sticks.add(scanner.nextInt());
    }
    return sticks;
}

StackExchange Code Review Q#123107, answer score: 5