Microsoft Online Assessment (OA) - Min Steps to Make Piles Equal Height

Given N piles of equal or unequal heights. In one step, You can remove any number of boxes from the pile which has the maximum height and try to make it equal to the one which is just lower than the maximum height of the stack. Determine the minimum number of steps required to make all of the piles equal in height.

Example 1:

Input: [5, 2, 1]

Output: 3

Explanation:

Step 1: reducing 5 -> 2 = [2, 2, 1] Step 2: reducing 2 -> 1 = [2, 1, 1] Step 3: reducing 2 -> 1 = [1, 1, 1]

Try it yourself

Implementation

1
-
from typing import List
1
+
from typing import Counter, List
2
2
3
3
def min_steps(nums: List[int]) -> int:
4
-
    # WRITE YOUR BRILLIANT CODE HERE
4
+
    cnt = Counter(nums)
5
-
    return 0
5
+
    nums = sorted(cnt.keys(), reverse=True)
6
+
    k, ans = 0, 0
7
+
    for x in nums[:-1]:
8
+
        k += cnt[x]
9
+
        ans += k
10
+
    return ans
11
+
6
12
if __name__ == '__main__':
7
13
    nums = [int(x) for x in input().split()]
8
14
    res = min_steps(nums)
9
15
    print(res)