Recent Tutorials and Articles
    HackerRank Solution: Cut the Sticks
    Published on: 17th July 2016

    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: 17th July 2016

    Comment Form is loading comments...