Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:
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.nums strictly smaller than largest. Let its value be nextLargest.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 * 104To solve this problem, we can first sort the array. After sorting, for each distinct number except the smallest one, count how many times smaller numbers need to be stepped up to equal the larger ones. Iterate over the sorted array and accumulate these steps until all numbers are equal.
In this C implementation, we use the qsort function to sort the array. Then, we iterate through the sorted array, counting distinct elements. Each time a new distinct element is found, it represents a level of operations needed to equalize numbers, accumulated into 'operations'.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) as sorting is done in place.
This approach involves counting the duplicates of each number without explicitly sorting. By iterating from the maximum value to the minimum, we calculate how many numbers need to be converted at each step by leveraging the array structure and gaps between numbers.
We maintain a count array for each potential value of the elements in nums. From the largest possible value, we calculate the cumulative operations needed by summing through the stored counts for all numbers greater than the current one.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + k) where k is the maximum possible value in nums, Space Complexity: O(k) for the count array.
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Iteration | Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) as sorting is done in place. |
| Approach 2: Counting and Aggregating | Time Complexity: O(n + k) where k is the maximum possible value in nums, Space Complexity: O(k) for the count array. |
Minimum Operations to Make Binary Array Elements Equal to One I - Leetcode 3191 - Python • NeetCodeIO • 7,612 views views
Watch 9 more video solutions →Practice Reduction Operations to Make the Array Elements Equal with our built-in code editor and test cases.
Practice on FleetCode