Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Cut the sticks challenge

Sharing is caring!

Problem statement
You are given N 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 N sticks, print the number of sticks that are left before each subsequent cut operations.

Note: For each cut operation, you have to re-calcuate the length of smallest sticks (excluding zero-length sticks).

Solution
We can use a PriorityQueue to solve this problem. The Java PriorityQueue implementation provides \mathcal{O}(\log n) time for the enqueing and dequeing methods (offer, poll, remove and add). Linear time for the remove(Object) and contains(Object) methods and constant time for the retrieval methods (peek, element, and size).

Full code

public class CutTheSticks {

    private static void solve(PriorityQueue minHeap, int n) {
        PriorityQueue newHeap = new PriorityQueue();
        do {
            System.out.println(minHeap.size());
            int min = minHeap.peek();
            while (!minHeap.isEmpty()) {
                int tmp = minHeap.poll();
                if (tmp != min) {
                    newHeap.add(tmp - min);
                }
            }

            minHeap.addAll(newHeap);
            newHeap.clear();
        } while (!minHeap.isEmpty());
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        PriorityQueue minHeap = new PriorityQueue();

        for (int i = 0; i < n; i++) {
            minHeap.add(in.nextInt());
        }

        solve(minHeap, n);
    }
}