Recent Tutorials and Articles
HackerRank Solution: Cut the Sticks
Published on: 25th May 2018

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: a0, a1,...aN-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 < ai < 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.

Published on: 25th May 2018