Minimum Operations to Make Array Equal
Problem
An integer n describes a hidden array arr of length n with arr[i] = 2·i + 1 — the first n odd numbers. In one operation you pick two indices x and y, subtract 1 from arr[x] and add 1 to arr[y]. Return the minimum number of operations needed to make every element of arr equal (1 ≤ n ≤ 10⁴; the answer fits in 32 bits).
n = 69def min_operations(n):
# arr[i] = 2*i + 1, so the total sum is n*n and the mean is n
target = n
ops = 0
for i in range(n // 2):
ops += target - (2 * i + 1) # gap below the mean
# arithmetic series: ops == n*n // 4
return opsfunction minOperations(n) {
// arr[i] = 2*i + 1, so the total sum is n*n and the mean is n
const target = n;
let ops = 0;
for (let i = 0; i < Math.floor(n / 2); i++) {
ops += target - (2 * i + 1); // gap below the mean
}
// arithmetic series: ops === Math.floor(n * n / 4)
return ops;
}int minOperations(int n) {
// arr[i] = 2*i + 1, so the total sum is n*n and the mean is n
int target = n;
int ops = 0;
for (int i = 0; i < n / 2; i++) {
ops += target - (2 * i + 1); // gap below the mean
}
// arithmetic series: ops == n * n / 4
return ops;
}int minOperations(int n) {
// arr[i] = 2*i + 1, so the total sum is n*n and the mean is n
int target = n;
int ops = 0;
for (int i = 0; i < n / 2; i++) {
ops += target - (2 * i + 1); // gap below the mean
}
// arithmetic series: ops == n * n / 4
return ops;
}Explanation
The key observation is that every operation is a transfer: one element loses 1 while another gains 1, so the total sum never changes. The sum of the first n odd numbers is 1 + 3 + … + (2n−1) = n², so when all elements finally agree, each must equal the mean n² / n = n. The target value is forced before we move a single unit.
The array is perfectly symmetric around that mean: arr[i] sits exactly as far below n as its mirror arr[n−1−i] sits above it, because n − (2i+1) = (2(n−1−i)+1) − n. So every unit a low element needs can come straight from its mirror — one decrement and one increment per operation, with nothing wasted. The total work is therefore exactly the sum of the gaps on the lower half, which is both a lower bound and achievable.
Walking through the default example n = 6: arr = [1, 3, 5, 7, 9, 11] and the target is 6. The lower half needs 6−1 = 5, 6−3 = 3, and 6−5 = 1 units, donated by the mirrors 11, 9, and 7 respectively. Summing the gaps gives 5 + 3 + 1 = 9 operations.
Those gaps form an arithmetic series — n−1, n−3, n−5, … stepping down by 2 for ⌊n/2⌋ terms — so the loop collapses to a closed form: ops = n²/4 when n is even and (n²−1)/4 when n is odd, i.e. ⌊n²/4⌋ in both cases. For n = 6 that is ⌊36/4⌋ = 9, matching the loop.
The loop shown in the code runs ⌊n/2⌋ times, so it is O(n) time with O(1) extra space; replacing it with the closed form n*n // 4 makes the whole solution O(1). The visualization keeps the loop so each gap and its mirror donation can be watched one element at a time.