REL102 - Editorial

PROBLEM LINK:

Practice 

Contest

Author: Divyesh Savaliya 

Editorialist: Divyesh Savaliya

DIFFICULTY:

Easy

PREREQUISITES:

Sorting

PROBLEM:

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).

EXPLANATION:

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 SOLUTIONS:

Author’s solution can be found here.