LeetCode 1551 - Minimum Operations to Make Array Equal

Difficulty: 🟡 Medium
Topics: Math

Solution

Problem Understanding

The problem presents an array arr of length n where each element is defined by the formula arr[i] = 2 * i + 1. This generates an array of consecutive odd numbers starting from 1. The task is to make all elements equal using a specific operation: choose two indices x and y, subtract 1 from arr[x] and add 1 to arr[y]. The goal is to minimize the number of such operations to make the array elements equal.

The input n represents the size of the array, and the output is the minimum number of operations required. The constraints 1 <= n <= 10^4 indicate that a naive approach simulating each operation would be too slow, so we need a mathematical or pattern-based solution. Edge cases include very small arrays like n = 1 where no operations are needed, and even versus odd n because the array is symmetric around the middle.

The problem guarantees that it is always possible to make the array elements equal, which is helpful because we do not need to check for impossibility.

Approaches

Brute Force

The brute force approach would simulate each operation: repeatedly find the maximum and minimum elements, decrement the max and increment the min, and count the operations until all elements are equal. This approach works because each operation reduces the difference between the largest and smallest numbers. However, it is too slow for large n because each operation changes only two elements and there can be up to O(n^2) differences to balance.

Optimal

The optimal approach leverages symmetry. The array [1, 3, 5, ..., 2n-1] is symmetric around its median. To equalize the array, each element's difference from the median contributes to the total number of operations. Specifically, the number of operations equals the sum of differences between the first half of the array and the median. This reduces the problem to a simple arithmetic series calculation.

The key insight is that the array's median is always n (since arr has consecutive odd numbers). For the first half of the array, we sum median - arr[i] for i in the first half, which gives a closed-form formula:

If n is even, the number of operations is (n/2) * (n/2).
If n is odd, the number of operations is (n//2) * ((n//2) + 1).

This allows constant-time computation without simulation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Simulate each operation by finding max and min repeatedly
Optimal	O(1)	O(1)	Use symmetry and arithmetic series formula based on array median

Algorithm Walkthrough

Calculate the median of the array. For arr[i] = 2*i + 1, the median is n because the array consists of n consecutive odd numbers starting from 1.
Determine the number of elements in the first half: half = n // 2. These elements are less than the median.
Compute the total operations required as the sum of differences between the median and each element in the first half. For the first half numbers, the sum of differences forms an arithmetic series 2, 4, 6, ..., 2*half.
Use the formula for the sum of the first half positive integers and multiply by 1 (since each difference contributes exactly one operation per unit difference) to get the result: operations = half * (n - half).
Return the computed number of operations.

Why it works: Each operation reduces the difference between an element below the median and one above it by 2, effectively moving two numbers closer to the median. Summing differences of elements below the median gives the exact number of unit changes needed, and by symmetry, the same number of operations applies to elements above the median. This ensures all elements converge to the median optimally.

Python Solution

class Solution:
    def minOperations(self, n: int) -> int:
        half = n // 2
        return half * (n - half)

The Python implementation first calculates half as n // 2. This represents the number of elements below the median. Then, it multiplies half by (n - half), which accounts for the arithmetic sum of differences to the median. The computation is direct and avoids loops, making it efficient for large n.

Go Solution

func minOperations(n int) int {
    half := n / 2
    return half * (n - half)
}

In Go, integer division automatically truncates toward zero, so n / 2 correctly computes half. The multiplication half * (n - half) is the same formula as Python. No extra handling is required because the constraints guarantee 1 <= n <= 10000, so integer overflow is not a concern.

Worked Examples

Example 1: `n = 3`

Array: [1, 3, 5]

Median: 3

Half = 3 // 2 = 1

Operations = 1 * (3 - 1) = 2

Step-by-step:

Step	Array State	Operation
Start	[1, 3, 5]	-
1	[2, 3, 4]	move 1 from 5 to 1
2	[3, 3, 3]	move 1 from 4 to 2

Example 2: `n = 6`

Array: [1, 3, 5, 7, 9, 11]

Median: 6

Half = 6 // 2 = 3

Operations = 3 * (6 - 3) = 9

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	The formula directly computes the result without iteration
Space	O(1)	Only a few integer variables are used

The optimal solution does not require building the array or simulating operations, making it extremely efficient.

Test Cases

# Basic examples
assert Solution().minOperations(3) == 2  # Example 1
assert Solution().minOperations(6) == 9  # Example 2

# Edge cases
assert Solution().minOperations(1) == 0  # Single element, no operations needed
assert Solution().minOperations(2) == 1  # Smallest even case
assert Solution().minOperations(4) == 4  # Small even n
assert Solution().minOperations(5) == 6  # Small odd n

# Large inputs
assert Solution().minOperations(10000) == 25000000  # Upper boundary test

Test	Why
n = 3	Validates small odd-sized array
n = 6	Validates small even-sized array
n = 1	Edge case, no operations needed
n = 2	Smallest even n
n = 10000	Stress test for large input

Edge Cases

Single Element (n = 1): The array [1] already has all elements equal, so the algorithm returns 0. This ensures the formula handles the smallest input correctly.

Even vs Odd n: The formula half * (n - half) works for both even and odd sizes. For even n, the two halves are equal, and for odd n, the formula still computes the sum of differences correctly by using integer division n // 2.

Large n: The solution handles the largest allowed value n = 10^4 without loops, avoiding performance issues. There is no risk of integer overflow in Python, and in Go, the maximum product 5000 * 5000 = 25,000,000 fits in a 32-bit integer.

This approach is fully robust and handles all constraints specified by the problem.