Hackerrank Cut the sticks Solution

Question

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<Integer> list = new ArrayList<Integer>(size);
    for(int i=0;i<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()>0)
        {
            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(Collections.singleton(0)); // remove the elements which are zero after cutting the sticks
            //System.out.println(list);
        }



   }

  }

Answer 1

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

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

List<Integer> list = new ArrayList<Integer>(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<Integer> sticks = readSticksFromStdin();
    Collections.sort(sticks);

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

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

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

Answer 2

Design

First of all, it would be nice to split the contents of main into two static methods:

• askUserForStickLengths(): uses a Scanner to load a list of integers representing the stick lengths.
• cutSticks: doing the actual cutting.

Efficiency

You sort the sticks into ascending order and you remove always the first stick first. The problem with that is that your list will have to shift all the elements one position towards the beginning of the list: so, if you have \$n\$ sticks, taking out the first will take \$\Theta(n)\$ time.

Instead, you could sort the sticks into descending order and keep removing the last stick (which is \$\Theta(1)\$ per stick).

However, note that the above are rather minor optimisations that cannot improve the overall running time. The worst-case running time of my and your algorithms is still \$\Theta(n^2)\$.

Summa summarum

All in all, I had this in mind:

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

public class CutSticks {

    public static List<Integer> askUserForStickLengths() {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        List<Integer> list = new ArrayList<>(size);

        for (int i = 0; i < size; ++i) {
            int length = scanner.nextInt();

            if (length < 0) {
                throw new IllegalArgumentException(
                        "Sticks of negative length are not allowed. Received " +
                        "a stick length " + length + ".");
            }

            list.add(length);
        }

        list.removeAll(Collections.<Integer>singleton(0));
        return list;
    }

    public static List<Integer> cutSticks(List<Integer> stickLengthList) {
        List<Integer> ret = new ArrayList<>(stickLengthList.size());

        // Sort the stick lengths into DESCENDING order.
        Collections.<Integer>sort(stickLengthList, 
                                  (a, b) -> { return b - a; });

        while (!stickLengthList.isEmpty()) {
            int listSize = stickLengthList.size();
            int smallestStickLength = stickLengthList.get(listSize - 1);

            for (int i = 0; i < listSize; ++i) {
                int currentStickLength = stickLengthList.get(i);
                stickLengthList.set(i, 
                                    currentStickLength - smallestStickLength);
            }

            ret.add(listSize);
            prune(stickLengthList);
        }

        return ret;
    }

    // Assumes that the input list is in descending order. We start removing the
    // "zero sticks" from the end of the list. As soon as we get to a non-zero
    // entry, we can return as the invariant guarantees there is no other 
    // zero length sticks.
    private static void prune(List<Integer> stickLengthList) {
        for (int i = stickLengthList.size() - 1; i >= 0; --i) {
            if (stickLengthList.get(i) == 0) {
                stickLengthList.remove(i);
            } else {
                return;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(cutSticks(askUserForStickLengths()));
    }
}