An alchemist's bench holds n cauldrons in a row; cauldron i currently contains a_i units of raw essence, where 0 means that cauldron is already empty. In one draining round, the alchemist finds the smallest nonzero amount currently present among all the cauldrons, and drains exactly that amount from every cauldron that still holds a nonzero amount (cauldrons that are already empty are left untouched). The alchemist repeats draining rounds until every cauldron reads 0. Determine how many rounds this takes.
n, the number of cauldrons.n non-negative integers a_1, a_2, ..., a_n, the starting amount in each cauldron.A single integer: the number of draining rounds needed to empty every cauldron.
Example 1
Input
5 7 3 7 0 5
Expected
3
Explanation
Round 1: the smallest nonzero amount is 3, so every nonzero cauldron loses 3: [4,0,4,0,2]. Round 2: the smallest nonzero amount is now 2, subtract from nonzero cauldrons: [2,0,2,0,0]. Round 3: the smallest nonzero amount is 2, subtract: [0,0,0,0,0]. It took 3 rounds, matching the 3 distinct nonzero starting values {7,3,5}.
Example 2
Input
4 0 0 0 0
Expected
0
Explanation
Every cauldron already reads 0, so no draining round is ever needed. The answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →