Cut the Sticks
Cut the Sticks is a programming problem and an interview question. The problem statement and the solution are given below.
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:
|
1 2 3 |
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:
|
1 2 3 |
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 ai represents the length of the ith 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 0
|
1 2 3 4 |
6 5 4 4 2 2 8 |
Sample Output 0
|
1 2 3 4 5 6 |
6 4 2 1 |
Sample Input 1
|
1 2 3 4 |
8 1 2 3 4 3 3 2 1 |
Sample Output 1
|
1 2 3 4 5 6 |
8 6 4 1 |
Explanation
Sample Case 0 :
|
1 2 3 4 5 6 7 |
sticks-length length-of-cut sticks-cut 5 4 4 2 2 8 2 6 3 2 2 _ _ 6 2 4 1 _ _ _ _ 4 1 2 _ _ _ _ _ 3 3 1 _ _ _ _ _ _ DONE DONE |
Sample Case 1
|
1 2 3 4 5 6 7 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
import java.util.ArrayList; import java.util.Scanner; public class Solution { public static void main(String[] args) { try(Scanner scanner = new Scanner(System.in)){ // read the number of sticks int N = scanner.nextInt(); if (N < 1){ return; } // read the length of the sticks // determine the smallest length ArrayList<Integer> input = new ArrayList<Integer>(); int smallest = Integer.MAX_VALUE; for (int i = 0; i < N; i++) { int temp = scanner.nextInt(); if (temp < smallest){ smallest = temp; } input.add(temp); } // Cut the sticks by the smallest length identified above. // Identify the smallest stick after the cut. Add the sticks to a // new list. Drop the ones with zero lengths. while( !input.isEmpty() ){ System.out.println(input.size()); ArrayList<Integer> nextInput = new ArrayList<Integer>(); int nextSmallest = Integer.MAX_VALUE; for (int i : input) { i = i - smallest; if (i > 0){ nextInput.add(i); if (i < nextSmallest){ nextSmallest = i; } } } input.clear(); input.addAll(nextInput); smallest = nextSmallest; } } // try ends } // main ends } // class Solution ends |
