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:
1. largest = 5 at index 0. nextLargest = 3. Reduce nums[0] to 3. nums = [3,1,3].
2. largest = 3 at index 0. nextLargest = 1. Reduce nums[0] to 1. nums = [1,1,3].
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:
1. largest = 3 at index 4. nextLargest = 2. Reduce nums[4] to 2. nums = [1,1,2,2,2].
2. largest = 2 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1,2,2].
3. largest = 2 at index 3. nextLargest = 1. Reduce nums[3] to 1. nums = [1,1,1,1,2].
4. largest = 2 at index 4. nextLargest = 1. Reduce nums[4] to 1. nums = [1,1,1,1,1].
Constraints:
1 <= nums.length <= 5 * 1041 <= nums[i] <= 5 * 104
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
| class Solution:
def reductionOperations(self, nums: List[int]) -> int:
nums.sort()
ans = cnt = 0
for i, v in enumerate(nums[1:]):
if v != nums[i]:
cnt += 1
ans += cnt
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int reductionOperations(int[] nums) {
Arrays.sort(nums);
int ans = 0, cnt = 0;
for (int i = 1; i < nums.length; ++i) {
if (nums[i] != nums[i - 1]) {
++cnt;
}
ans += cnt;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int reductionOperations(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 0, cnt = 0;
for (int i = 1; i < nums.size(); ++i) {
cnt += nums[i] != nums[i - 1];
ans += cnt;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
| func reductionOperations(nums []int) int {
sort.Ints(nums)
ans, cnt := 0, 0
for i, v := range nums[1:] {
if v != nums[i] {
cnt++
}
ans += cnt
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| function reductionOperations(nums: number[]): number {
nums.sort((a, b) => a - b);
let ans = 0;
let cnt = 0;
for (let i = 1; i < nums.length; ++i) {
if (nums[i] != nums[i - 1]) {
++cnt;
}
ans += cnt;
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class Solution {
public int ReductionOperations(int[] nums) {
Array.Sort(nums);
int ans = 0, up = 0;
for (int i = 1; i < nums.Length; i++) {
if (nums[i] != nums[i - 1]) {
up++;
}
ans += up;
}
return ans;
}
}
|
Solution 2#
1
2
3
4
5
6
7
| class Solution:
def reductionOperations(self, nums: List[int]) -> int:
ans = cnt = 0
for _, v in sorted(Counter(nums).items()):
ans += cnt * v
cnt += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int reductionOperations(int[] nums) {
Map<Integer, Integer> tm = new TreeMap<>();
for (int v : nums) {
tm.put(v, tm.getOrDefault(v, 0) + 1);
}
int ans = 0, cnt = 0;
for (int v : tm.values()) {
ans += cnt * v;
++cnt;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int reductionOperations(vector<int>& nums) {
map<int, int> m;
for (int v : nums) ++m[v];
int ans = 0, cnt = 0;
for (auto [_, v] : m) {
ans += cnt * v;
++cnt;
}
return ans;
}
};
|
