1887.reduction-operations-to-make-the-array-elements-equal.md

1887. Reduction Operations to Make the Array Elements Equal

Hints

• What happens if you sort the array? Can you process from smallest to largest or vice versa?
• Try to group the same numbers together and think about how many steps each group needs.

Breakdowns

1. What is the minimum number of operations to make all elements equal?

• Each operation reduces the largest element to the next largest. If you sort the array, you can process from largest to smallest, counting how many times each unique value needs to be reduced to the next smaller value.

2. Can you use prefix sums or a running count to simplify the calculation?

• By iterating through the sorted array, you can accumulate the number of operations needed for each unique value.

Two Pointers (Group by Consecutive)

The key idea is to sort the array and count, for each unique value, how many operations are needed to reduce all larger values to it.

// After sorting
..., A, B, B, B, C, C, D, D, D, D
|----|  |-----|  |--|  |--------|
     ^ The minimum number
     A <-  B // 1 step
     A <-  B  <- C // 2 steps
     A <-  B  <- C  <- D // 3 steps

...A, ...B, ...C, ...D, ...E
   0     1     2     3     4 steps

Value	Steps to Reduce to A	Count	Total Steps Needed
B	1 (B -> A)	3	3 × 1 = 3
C	2 (C -> B -> A)	2	2 × 2 = 4
D	3 (D -> C -> B -> A)	4	4 × 3 = 12
E	4 (E -> D -> C -> B -> A)	...	... × 4 = ... (and so on)

So we have to count the consecutive same value, and the operation for that number to reduce is steps * count. Each time you encounter a new value, you increment the step count.

W, X, Y, Z // ascending order
a, b, c, d // count
0  1  2  3 // steps
         d // Change all `Z` to `X`
      c, d // Change all `Y` to `X`
   b, c, d // Change all `X` to `Y`

The total number of operations is: b + 2 * c + 3 * d.

fun reductionOperations(nums: IntArray): Int {
    nums.sort()
    val n = nums.size
    var ans = 0
    var steps = 0
    var i = 0
    while (i < n) {
        val start = i
        i++
        while (i < n && nums[i] == nums[start]) {
            i++
        }
        ans += steps * (i - start)
        steps++
    }
    return ans
}

Or equivalently, we can use a running count to accumulate the number of operations needed for each unique value.

fun reductionOperations(nums: IntArray): Int {
    nums.sort()
    var ans = 0
    var steps = 0
    for (i in 1 until nums.size) {
        if (nums[i] != nums[i - 1]) {
            steps++
        }
        ans += steps
    }
    return ans
}

The following approach is more complex than above, might skip it first.

This is an alternative approach that uses the "group by consecutive" pattern, we can group the numbers W, X, Y, Z in descending order and count the number of elements in each group a, b, c, d:

|---W---|---X---|---Y---|---Z---|
|---a---|---b---|---c---|---d---|

Then start the operation to reduce the largest to the second largest, second largest to the third largest, and so on until all the numbers are Z (the smallest number):

1. We need a operations to make all W to X.

2. Next, we reduce all X to Y: We need a + b operations to make all X to Y.

3. Finally, we reduce all Y to Z: We need a + b + c operations to make all Y to Z.

So the total number of operations is a + (a + b) + (a + b + c).

// Sort the array in descending order
|---W---|---X---|---Y---|---Z---|

// Reduce all `W` to `X`
|-------X-------|---Y---|---Z---|

// Reduce all `X` to `Y`
|---------------Y-------|---Z---|
|

// Reduce all `Y` to `Z`
|-----------------------Z-------|

fun reductionOperations(nums: IntArray): Int {
    val n = nums.size
    nums.sortDescending()
    val last = nums.last()
    var i = 0
    var ans = 0
    var count = 0
    while (i < n) {
        var start = i
        if (nums[start] == last) break
        i++
        while (i < n && nums[i] == nums[start]) {
            i++
        }
        count += (i - start)
        ans += count
    }
    return ans
}

All solutions above are the same complexity:

• Time Complexity: O(n log n)
• Space Complexity: O(log n) for sorting.

WA

fun reductionOperations(nums: IntArray): Int {
    val n = nums.size
    nums.sortDescending()
    val last = nums.last()
    var i = 0
    var ans = 0
    while (i < n) {
        var start = i
        if (nums[start] == last) break
        i++
        while (i < n && nums[i] == nums[start]) {
            i++
        }
        // Wrong way to calculate accumulated number of operations
        ans += ans + (i - start)
    }
    return ans
}

Edge Cases

• All elements are already equal: answer is 0.
• Only two unique values: answer is the count of the larger value.
• Large input with many duplicates: make sure to group correctly and avoid overcounting.

Similar or Follow-up Problems

• 945. Minimum Increment to Make Array Unique
• 1775. Equal Sum Arrays With Minimum Number of Operations