Formatted question description: https://leetcode.ca/all/1887.html

# 1887. Reduction Operations to Make the Array Elements Equal

## Level

Medium

## Description

Given an integer array `nums`

, your goal is to make all elements in `nums`

equal. To complete one operation, follow these steps:

- Find the
**largest**value in`nums`

. Let its index be`i`

(**0-indexed**) and its value be`largest`

. If there are multiple elements with the largest value, pick the smallest`i`

. - Find the
**next largest**value in`nums`

**strictly smaller**than`largest`

. Let its value be`nextLargest`

. - Reduce
`nums[i]`

to`nextLargest`

.

Return *the number of operations to make all elements in nums equal*.

**Example 1:**

**Input:** nums = [5,1,3]

**Output:** 3

**Explanation:** It takes 3 operations to make all elements in nums equal:

- largest = 5 at index 0. nextLargest = 3. Reduce nums[0] to 3. nums = [3,1,3].
- largest = 3 at index 0. nextLargest = 1. Reduce nums[0] to 1. nums = [1,1,3].
- largest = 3 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1].

**Example 2:**

**Input:** nums = [1,1,1]

**Output:** 0

**Explanation:** All elements in nums are already equal.

**Example 3:**

**Input:** nums = [1,1,2,2,3]

**Output:** 4

**Explanation:** It takes 4 operations to make all elements in nums equal:

- largest = 3 at index 4. nextLargest = 2. Reduce nums[4] to 2. nums = [1,1,2,2,2].
- largest = 2 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1,2,2].
- largest = 2 at index 3. nextLargest = 1. Reduce nums[3] to 1. nums = [1,1,1,1,2].
- largest = 2 at index 4. nextLargest = 1. Reduce nums[4] to 1. nums = [1,1,1,1,1].

**Constraints:**

`1 <= nums.length <= 5 * 10^4`

`1 <= nums[i] <= 5 * 10^4`

## Solution

Use a tree map to store the elements and the number of occurrences in `nums`

. Each time find `largest`

which is the largest key in the tree map and `nextLargest`

which is the largest key that is less than `largest`

in the tree map, add the corresponding value of `largest`

to the number of operations and to the value of `nextLargest`

, and remove `largest`

from the tree map. Repeat the process until the tree map’s size is 1. Finally, return the number of operations.

```
class Solution {
public int reductionOperations(int[] nums) {
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
for (int num : nums)
map.put(num, map.getOrDefault(num, 0) + 1);
int operations = 0;
while (map.size() > 1) {
int largest = map.lastKey();
int nextLargest = map.floorKey(largest - 1);
int curOperations = map.get(largest);
operations += curOperations;
map.remove(largest);
map.put(nextLargest, map.get(nextLargest) + curOperations);
}
return operations;
}
}
```