Reduction Operations to Make the Array Elements Equal

Reduction Operations to Make the Array Elements Equal - Problem

Array Sorting Medium

Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:

Find the largest value in 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.
Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.
Reduce nums[i] to nextLargest.

Return the number of operations to make all elements in nums equal.

Input & Output

Example 1 — Basic Reduction

$ Input: nums = [5,1,3]

› Output: 3

💡 Note: Step by step: [5,1,3] → [3,1,3] → [1,1,3] → [1,1,1]. Total of 3 operations.

Example 2 — Already Equal

$ Input: nums = [1,1,1]

› Output: 0

💡 Note: All elements are already equal, so no operations needed.

Example 3 — Multiple Same Values

$ Input: nums = [1,1,2,2,3]

› Output: 4

💡 Note: [1,1,2,2,3] → [1,1,2,2,2] → [1,1,1,2,2] → [1,1,1,1,2] → [1,1,1,1,1]. Total of 4 operations.

Constraints

1 ≤ nums.length ≤ 5 × 10⁴
1 ≤ nums[i] ≤ 5 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array with different values: [5,1,3]

Reduction Process

Repeatedly reduce largest to next largest

Output

Count total operations needed: 3

Key Takeaway

🎯 Key Insight: Instead of simulating step by step, count frequencies and calculate operations mathematically by processing unique values in descending order.

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to avoid simulating the process and instead calculate operations mathematically. Count unique values and their frequencies, then process from largest to smallest. Each reduction level affects all elements that need to pass through it. Best approach uses sorting and frequency counting with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Simulation Approach	O(n²)	O(1)	Simulate the actual reduction process step by step
Sort and Count Approach	O(n log n)	O(n)	Sort unique values first, then calculate operations mathematically

Simulation Approach — Algorithm Steps

Find the largest element and its index
Find the next largest value
Reduce the largest to next largest
Repeat until all elements equal

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Maximum

Locate the largest element in the array

Find Next Largest

Find the next smaller unique value

Reduce

Replace max with next largest value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int n) {
    // Create a copy
    int* numsCopy = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        numsCopy[i] = nums[i];
    }
    
    int operations = 0;
    
    while (1) {
        // Find the largest value and its index
        int maxVal = numsCopy[0];
        int maxIdx = 0;
        for (int i = 1; i < n; i++) {
            if (numsCopy[i] > maxVal) {
                maxVal = numsCopy[i];
                maxIdx = i;
            }
        }
        
        // Check if all elements are equal
        int allEqual = 1;
        for (int i = 0; i < n; i++) {
            if (numsCopy[i] != maxVal) {
                allEqual = 0;
                break;
            }
        }
        if (allEqual) break;
        
        // Find the next largest value
        int nextLargest = INT_MIN;
        for (int i = 0; i < n; i++) {
            if (numsCopy[i] < maxVal && numsCopy[i] > nextLargest) {
                nextLargest = numsCopy[i];
            }
        }
        
        // Reduce the largest element
        numsCopy[maxIdx] = nextLargest;
        operations++;
    }
    
    free(numsCopy);
    return operations;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

In worst case, we need O(n) operations, each requiring O(n) time to find max and next max

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables for tracking indices and values

✓ Linear Space

38.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler