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.
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 recalculate the length of smallest sticks (excluding zero-length sticks).
You are initially given the height of N sticks. At each step, find the height of the smallest stick, say k, and cut a portion of length k from each stick. All those sticks with height k will disappear. Then print the number of the remaining sticks.
Repeat the above step until all the sticks disappear.
Time complexity is O(N log N).
Author’s solution can be found here.