0% completed
Problem Statement
Given an array of integers nums
, return the number of operations required to make all elements in nums
equal. To perform one operation, you can follow the below steps:
- Select the
maximum
element ofnums
. If there are multiple occurrences of the maximum element, choose the element which has lowest indexi
. - Select the
second largest
element ofnums
. - Replace the element at index
i
with the second largest element.
Examples
Example 1:
- Input:
[3, 5, 5, 2]
- Expected output:
5
- Justification:
- The largest element is 5. Reducing both 5s to 3 requires two operations.
- Update array will be [3, 3, 3, 2].
- Three more operations are needed to reduce the 3 to 2. The updated array will be [2, 2, 2, 2].
- A total five operations make all elements equal to 2.
Example 2:
- Input:
[11, 9, 7, 5, 3]
- Expected output:
10
- Justification:
- Each number needs to be reduced stepwise to the next smaller number until all are equal to the smallest number 3.
- 1 operation is required to convert 11 to 9. The updated array will be [9, 9, 7, 5, 3].
- 2 operations are required to convert 9 to 7. The updated array will be [7, 7, 7, 5, 3].
- 3 operations are required to convert 7 to 5. The updated array will be [5, 5, 5, 5, 3].
- 4 operations are required to convert 5 to 3. The updated array will be [3, 3, 3, 3, 3].
- Tota numbers of operations: 1 + 2 + 3 + 4 = 10.
Example 3:
- Input:
[8, 8, 8, 8]
- Expected output:
0
- Justification: All elements are already equal, so no operations are needed.
Constraints:
- 1 <= nums.length <= 5 * 10<sup>4</sup>
- 1 <= nums[i] <= 5 * 10<sup>4</sup>
Solution
To solve this problem, the most effective approach involves sorting the array and leveraging the sorted structure to determine the reduction operations efficiently. The solution is driven by identifying and counting the number of elements that must be reduced to each unique lesser value until all elements are the same. The frequency of each distinct value in the array provides a clear path for determining the number of necessary operations.
By sorting the array, we can work backwards, starting from the largest element, and reduce it step by step to match the next distinct element in the sorted order. This method ensures that the number of operations is minimized since we always reduce the largest elements first and in bulk, which decreases the number of total operations.
Step-by-step Algorithm
-
Sort the Array:
- Begin by sorting the given array of integers in non-decreasing order. This will organize the array such that the smallest elements are at the beginning and the largest at the end, facilitating efficient traversal for reductions.
-
Initialize Variables:
- Initialize a variable,
operations
, to zero. This will keep track of the total number of operations performed. - Initialize a variable,
count
, to one. This will count the number of occurrences of the current largest value we are reducing.
- Initialize a variable,
-
Traverse the Sorted Array from the End to the Start:
- Start from the last element of the array (which is the largest due to sorting) and move towards the first element.
- Check if the current element is different from the previous one:
- If it is, add the value of
count
tooperations
. This addition accounts for the operations needed to reduce all occurrences of the current largest element to the next largest element. - Increase the
count
by one for each step back through the array. This increment reflects that one more element (the previous element in the sorted array) will need to be reduced in the next round of operations.
- If it is, add the value of
-
Return the Result:
- Once the traversal is complete, return the
operations
variable, which now contains the total number of operations required to make all elements equal.
- Once the traversal is complete, return the
Algorithm Walkthrough
Let's consider the input: nums = [11, 9, 7, 5, 3]
-
Sort the Array:
- The array is already sorted in non-decreasing order:
[3, 5, 7, 9, 11]
.
- The array is already sorted in non-decreasing order:
-
Initialize Variables:
operations = 0
count = 1
-
Traverse the Sorted Array:
-
Start from the end of the array (index 4, value
11
). -
Index 4 (value
11
):- Compare with the next element towards the start (index 3, value
9
). - They are different, so add
count
tooperations
(0 + 1 = 1). - Increment
count
to 2.
- Compare with the next element towards the start (index 3, value
-
Index 3 (value
9
):- Compare with the next element towards the start (index 2, value
7
). - They are different, add
count
tooperations
(1 + 2 = 3). - Increment
count
to 3.
- Compare with the next element towards the start (index 2, value
-
Index 2 (value
7
):- Compare with the next element towards the start (index 1, value
5
). - They are different, add
count
tooperations
(3 + 3 = 6). - Increment
count
to 4.
- Compare with the next element towards the start (index 1, value
-
Index 1 (value
5
):- Compare with the next element towards the start (index 0, value
3
). - They are different, add
count
tooperations
(6 + 4 = 10). - Increment
count
to 5.
- Compare with the next element towards the start (index 0, value
-
-
Complete Traversal:
- All elements have been checked, and operations needed to reduce each to the next smallest value have been counted.
-
Return the Result:
- The final value of
operations
is 10, indicating the total operations needed.
- The final value of
Code
Complexity Analysis
Time Complexity
- Sorting the array: The most computationally intensive operation here is sorting the array, which has a time complexity of O(n \log n), where (n) is the number of elements in the array.
- Traversing the sorted array: Once the array is sorted, the algorithm performs a single pass through the array to count the required operations, which is O(n).
Thus, the overall time complexity of the algorithm is O(n \log n).
Space Complexity
- Space for sorting: Sorting the array in place requires no additional space beyond the input array itself in some implementations like heapsort, but for languages or methods that use mergesort (like Java), this might require O(n) space.
- Counters: Only a few additional variables are used, which are constant space, O(1).
Therefore, the space complexity is O(1) if the sorting is done in place, or O(n) if extra space is used for sorting.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible