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.
1using System;
2
3public class Solution {
4 public int ReductionOperations(int[] nums) {
5 Array.Sort(nums);
6 int operations = 0, distinctCount = 0;
7 for (int i = 1; i < nums.Length; i++) {
8 if (nums[i] != nums[i - 1]) {
9 distinctCount++;
10 }
11 operations += distinctCount;
12 }
13 return operations;
14 }
15
16 public static void Main(string[] args) {
17 Solution solution = new Solution();
18 int[] nums = {5, 1, 3};
19 Console.WriteLine(solution.ReductionOperations(nums));
20 }
21}This C# solution mirrors the logic of the prior implementations. We sort the array and track distinct elements to calculate the total operations required, incrementing the operation counter at each step as new distinct elements are encountered.
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.
#include <vector>
int reductionOperations(std::vector<int>& nums) {
std::vector<int> count(50001, 0);
for (int num : nums) {
count[num]++;
}
int operations = 0, total = 0;
for (int i = 50000; i > 0; i--) {
if (count[i]) {
operations += total;
total += count[i];
}
}
return operations;
}
int main() {
std::vector<int> nums = {5, 1, 3};
std::cout << reductionOperations(nums) << std::endl;
return 0;
}This C++ solution tracks counts of each integer and processes from the highest possible integer down to compute operations. This enables efficient summation of the necessary steps by processing through accumulated frequencies.