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

1from typing import Counter, List
2
3def min_steps(nums: List[int]) -> int:
4    cnt = Counter(nums)
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
12if __name__ == '__main__':
13    nums = [int(x) for x in input().split()]
14    res = min_steps(nums)
15    print(res)
16
1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7    public static int minSteps(List<Integer> nums) {
8        int nums_size = nums.size();
9
10        if (nums_size < 2) {
11            return 0;
12        }
13
14        nums.sort(null);
15        int sum = 0;
16
17        for (int i = 1; i < nums_size; ++i) {
18            if (nums.get(nums_size - i - 1) != nums.get(nums_size - i)) {
19                sum += i;
20            }
21        }
22
23        return sum;
24    }
25
26    public static List<String> splitWords(String s) {
27        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
28    }
29
30    public static void main(String[] args) {
31        Scanner scanner = new Scanner(System.in);
32        List<Integer> nums = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
33        scanner.close();
34        int res = minSteps(nums);
35        System.out.println(res);
36    }
37}
38
1function minSteps(nums) {
2    const nums_size = nums.length;
3
4    if (nums_size < 2) {
5        return 0;
6    }
7    nums.sort();
8    let sum = 0;
9
10    for (let i = 1; i < nums_size; ++i) {
11        if (nums[nums_size - i - 1] !== nums[nums_size - i]) {
12            sum += i;
13        }
14    }
15    return sum;
16}
17
18function splitWords(s) {
19    return s == "" ? [] : s.split(' ');
20}
21
22function* main() {
23    const nums = splitWords(yield).map((v) => parseInt(v));
24    const res = minSteps(nums);
25    console.log(res);
26}
27
28class EOFError extends Error {}
29{
30    const gen = main();
31    const next = (line) => gen.next(line).done && process.exit();
32    let buf = '';
33    next();
34    process.stdin.setEncoding('utf8');
35    process.stdin.on('data', (data) => {
36        const lines = (buf + data).split('\n');
37        buf = lines.pop();
38        lines.forEach(next);
39    });
40    process.stdin.on('end', () => {
41        buf && next(buf);
42        gen.throw(new EOFError());
43    });
44}
45

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫