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 <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int reductionOperations(int* nums, int numsSize) {
9 qsort(nums, numsSize, sizeof(int), compare);
10 int operations = 0, distinctCount = 0;
11 for (int i = 1; i < numsSize; i++) {
12 if (nums[i] != nums[i - 1]) {
13 distinctCount++;
14 }
15 operations += distinctCount;
16 }
17 return operations;
18}
19
20int main() {
21 int nums[] = {5, 1, 3};
22 int size = sizeof(nums) / sizeof(nums[0]);
23 printf("%d\n", reductionOperations(nums, size));
24 return 0;
25}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'.
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.
public class Solution {
public int ReductionOperations(int[] nums) {
int[] count = new int[50001];
foreach (int num in nums) {
count[num]++;
}
int operations = 0, total = 0;
for (int i = 50000; i > 0; i--) {
if (count[i] > 0) {
operations += total;
total += count[i];
}
}
return operations;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {5, 1, 3};
Console.WriteLine(solution.ReductionOperations(nums));
}
}C# uses an integer array to maintain counts and iterates through it from top down, calculated cumulative operations by acknowledgment of all larger numbers already accounted for.