Welcome to Subscribe On Youtube

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:

  1. 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.
  2. Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.
  3. 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 * 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;
    }
}

############

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;
    }
}

  • // OJ: https://leetcode.com/problems/reduction-operations-to-make-the-array-elements-equal/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int reductionOperations(vector<int>& A) {
        map<int, int> m;
        for (int n : A) m[n]++;
        int step = 0, ans = 0;
        for (auto &[n, cnt] : m) {
            if (step > 0) ans += cnt * step;
            ++step;
        }
        return ans;
    }
};

  • 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

############

# 1887. Reduction Operations to Make the Array Elements Equal
# https://leetcode.com/problems/reduction-operations-to-make-the-array-elements-equal/

class Solution:
    def reductionOperations(self, nums: List[int]) -> int:
        mmin = min(nums)
        heap = []
        counter = collections.Counter(nums)
        for num,count in counter.items():
            if num != mmin:
                heap.append((-num, count))
        
        heapq.heapify(heap)
        
        res = 0
        while len(heap) > 0:
            num, count = heapq.heappop(heap)
            num = -num
            res += count
            
            if heap:
                nextNum, nextCount = heapq.heappop(heap)
                heapq.heappush(heap, (nextNum, nextCount + count))
        
        return res
        
            


  • 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
}

  • 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;
}


  • 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;
    }
}

All Problems

All Solutions