1887. Reduction Operations to Make the Array Elements Equal LeetCode Solution

In this guide, you will get 1887. Reduction Operations to Make the Array Elements Equal LeetCode Solution with the best time and space complexity. The solution to Reduction Operations to Make the Array Elements Equal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Reduction Operations to Make the Array Elements Equal solution in C++
Reduction Operations to Make the Array Elements Equal solution in Java
Reduction Operations to Make the Array Elements Equal solution in Python
Additional Resources

1887. Reduction Operations to Make the Array Elements Equal LeetCode Solution image

Problem Statement of Reduction Operations to Make the Array Elements Equal

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 * 104
1 <= nums[i] <= 5 * 104

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})

1887. Reduction Operations to Make the Array Elements Equal LeetCode Solution in C++

class Solution {
 public:
  int reductionOperations(vector<int>& nums) {
    int ans = 0;

    ranges::sort(nums);

    for (int i = nums.size() - 1; i > 0; --i)
      if (nums[i] != nums[i - 1])
        ans += nums.size() - i;

    return ans;
  }
};
/* code provided by PROGIEZ */

1887. Reduction Operations to Make the Array Elements Equal LeetCode Solution in Java

class Solution {
  public int reductionOperations(int[] nums) {
    int ans = 0;

    Arrays.sort(nums);

    for (int i = nums.length - 1; i > 0; --i)
      if (nums[i] != nums[i - 1])
        ans += nums.length - i;

    return ans;
  }
}
// code provided by PROGIEZ

1887. Reduction Operations to Make the Array Elements Equal LeetCode Solution in Python

class Solution:
  def reductionOperations(self, nums: list[int]) -> int:
    ans = 0

    nums.sort()

    for i in range(len(nums) - 1, 0, -1):
      if nums[i] != nums[i - 1]:
        ans += len(nums) - i

    return ans
 # code by PROGIEZ