Sponsored
Sponsored
To 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.
Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) as sorting is done in place.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int reductionOperations(std::vector<int>& nums) {
6 std::sort(nums.begin(), nums.end());
7 int operations = 0, distinctCount = 0;
8 for (int i = 1; i < nums.size(); i++) {
9 if (nums[i] != nums[i - 1]) {
10 distinctCount++;
11 }
12 operations += distinctCount;
13 }
14 return operations;
15}
16
17int main() {
18 std::vector<int> nums = {5, 1, 3};
19 std::cout << reductionOperations(nums) << std::endl;
20 return 0;
21}In C++, we utilize the sort function to order the elements. Similar to the C solution, we iterate through the sorted list, using a distinct count to track how many operations are needed to reach equality.
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.
Time Complexity: O(n + k) where k is the maximum possible value in nums, Space Complexity: O(k) for the count array.
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.