This tutorial provides Java solution to "Cut the sticks" challenge of HackerRank.

Hackerrank Challenge Details

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 recalcuate the length of smallest sticks (excluding zero-length sticks).

Input Format:

The first line contains a single integer N. 
The next line contains N integers: a₀, a₁,...a_N-1 separated by space, where  represents the length of the  stick.

Output Format:

For each operation, print the number of sticks that are cut, on separate lines.

Constraints:

• 1 < N < 1000
• 1 < a_i < 1000

Sample Input:

8
1 2 3 4 3 3 2 1

Sample Output:

8
6
4
1

Explanation:

sticks-length         length-of-cut   sticks-cut
1 2 3 4 3 3 2 1         1               8
_ 1 2 3 2 2 1 _         1               6
_ _ 1 2 1 1 _ _         1               4
_ _ _ 1 _ _ _ _         1               1
_ _ _ _ _ _ _ _       DONE            DONE

Solution Details

Java Implementation:

package com.saintech.allprogtutorials.hackerrank.algos;

import java.util.Scanner;

/**
 * @author Sain Technology Solutions
 * 
 * Solution to Problem - https://www.hackerrank.com/challenges/cut-the-sticks
 *
 */
public class CutTheSticks {
	
	public static void main(String[] args) {
		final Scanner in = new Scanner(System.in);
		final int N = in.nextInt();
		
		// Add all the stick lengths to an array of size 1000 since no of elements can't be 
		// more than 1000 as per constraints. Other option would be to add it in a sorted list or map
		// but that will require O(nlogn) time complexity in most cases.
		final int[] sticks = new int[1000];
		for(int i = 0; i < N; i++) {
			final int stickLen = in.nextInt();
			sticks[stickLen]++;
		}

		// Iterate over the sticks array and for each positive no of sticks, reduce the remaining sticks by that count.
		int remainingSticks =N;
		System.out.println(remainingSticks);
		for(int i = 0; i <sticks.length; i++) {
			if(sticks[i] > 0) {
				remainingSticks -= sticks[i];
				if(remainingSticks == 0) {
					break;
				}
				System.out.println(remainingSticks);
			}
		}
		
		in.close();
	}
}

Thank you for reading through the tutorial. In case of any feedback/questions/concerns, you can communicate same to us through your comments and we shall get back to you as soon as possible.