Problem

You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i (i.e., 0 <= i < n).

In one operation, you can select two indices x and y where 0 <= x, y < n and subtract 1 from arr[x] and add 1 to arr[y] (i.e., perform arr[x] -=1 and arr[y] += 1). The goal is to make all the elements of the array equal. It is guaranteed that all the elements of the array can be made equal using some operations.

Given an integer n, the length of the array, return the minimum number of operations needed to make all the elements of arr equal.

Examples

Example 1

1
2
3
4
5

Input: n = 3
Output: 2
Explanation: arr = [1, 3, 5]
First operation choose x = 2 and y = 0, this leads arr to be [2, 3, 4]
In the second operation choose x = 2 and y = 0 again, thus arr = [3, 3, 3].

Example 2

1
2

Input: n = 6
Output: 9

Constraints

  • 1 <= n <= 10^4

Solution

Method 1 – Math & Two Pointers

Intuition

The array is always odd numbers: [1, 3, 5, …]. To make all elements equal, we want every element to become the median. The minimum number of operations is the sum of differences between each element and the median, but with the allowed operation, it can be calculated by pairing the smallest and largest, then moving them towards the median.

Approach

  1. The target value for all elements is the median of the array, which is always n (since arr[i] = 2*i+1, median is n).
  2. For each i from 0 to n//2-1, pair arr[i] and arr[n-1-i].
  3. The number of operations needed for each pair is arr[n-1-i] - n.
  4. Sum up the operations for all pairs.
  5. Alternatively, the answer is sum_{i=0}^{n//2-1} (n - arr[i])
  6. Formula simplifies to n//2 * n.

Code

1
2
3
4
5
6

class Solution {
public:
    int minOperations(int n) {
        return (n / 2) * ((n + 1) / 2);
    }
};
1
2
3

func minOperations(n int) int {
    return (n / 2) * ((n + 1) / 2)
}
1
2
3
4
5

class Solution {
    public int minOperations(int n) {
        return (n / 2) * ((n + 1) / 2);
    }
}
1
2
3
4
5

class Solution {
    fun minOperations(n: Int): Int {
        return (n / 2) * ((n + 1) / 2)
    }
}
1
2
3

class Solution:
    def minOperations(self, n: int) -> int:
        return (n // 2) * ((n + 1) // 2)
1
2
3
4
5

impl Solution {
    pub fn min_operations(n: i32) -> i32 {
        (n / 2) * ((n + 1) / 2)
    }
}
1
2
3
4
5

class Solution {
    minOperations(n: number): number {
        return Math.floor(n / 2) * Math.floor((n + 1) / 2);
    }
}

Complexity

  • ⏰ Time complexity: O(1) — Only arithmetic operations, no loops or recursion.
  • 🧺 Space complexity: O(1) — No extra space used.