PROBLEM LINK:
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.