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:

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:

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

Sample Output 0

Sample Input 1

Sample Output 1

Explanation

Sample Case 0 :

Sample Case 1

 

Solution

 

 

Leave a Reply

avatar
300
  Subscribe  
Notify of