# Minimum Operations to Make Array Equal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-make-array-equal)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-array-equal
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## 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.

**Example 1:**

**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:**

**Input:** n = 6
**Output:** 9

**Constraints:**

* `1 <= n <= 104`

# Approaches
## Simulation with Array Construction
This approach simulates the problem by first constructing the array as described, then calculating the target value, and finally iterating through the array to sum up the necessary operations.
**Time:** O(n) - We iterate through the array twice: once to populate it (O(n)) and once to calculate the operations for the first half (O(n/2)). This simplifies to O(n). · **Space:** O(n) - We explicitly create an integer array of size `n` to store the values.
**Pros:** Simple to understand and directly follows the problem description.
**Cons:** Inefficient in terms of space, as creating the array is not strictly necessary and consumes memory proportional to `n`.
### Explanation
The core idea is to determine the final equal value all elements must have. Since each operation subtracts 1 from one element and adds 1 to another, the total sum of the array elements remains constant. Therefore, the final value for each element must be the average of the initial elements.

The array is an arithmetic progression `1, 3, 5, ...`. The sum of its `n` elements is `n^2`. Thus, the target value for each element is `n^2 / n = n`.

The number of operations is the total amount that needs to be added to elements smaller than the target `n`. We only need to consider the first half of the array, as these are the elements smaller than `n`. The elements in the second half are symmetrically larger than `n`.

```java
class Solution {
    public int minOperations(int n) {
        if (n <= 1) {
            return 0;
        }
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = (2 * i) + 1;
        }
        
        int target = n;
        int operations = 0;
        for (int i = 0; i < n / 2; i++) {
            operations += target - arr[i];
        }
        
        return operations;
    }
}
```
### Algorithm
*   Create an integer array `arr` of size `n`.
*   Populate the array such that `arr[i] = (2 * i) + 1` for `i` from `0` to `n-1`.
*   Initialize a variable `operations` to 0.
*   The target value for all elements to be equal is `n`.
*   Iterate from `i = 0` to `n / 2 - 1`. The elements in this range are all smaller than the target `n`.
*   For each `arr[i]`, calculate the difference `n - arr[i]` and add it to `operations`.
*   Return `operations`.

## Iterative Calculation without Array
This approach improves upon the first one by avoiding the explicit creation of the array. Since the value of each element `arr[i]` can be calculated on-the-fly using the formula `(2 * i) + 1`, we can iterate and sum the required operations without storing the entire array in memory.
**Time:** O(n) - The loop runs `n / 2` times, making the time complexity linear with respect to `n`. · **Space:** O(1) - This approach uses only a few variables to store the running total and loop counter, regardless of the size of `n`. No extra space proportional to `n` is used.
**Pros:** Space-efficient compared to the simulation approach, using O(1) space.; Still relatively easy to follow the logic.
**Cons:** Not the most optimal solution as a closed-form mathematical formula exists, which can solve the problem in constant time.
### Explanation
Similar to the previous approach, we identify that the target value for all elements is `n`. The total number of operations is the sum of differences `(target - arr[i])` for all elements `arr[i]` that are smaller than the target.

The elements `arr[i]` are smaller than the target `n` for indices `i` from `0` to `n / 2 - 1`.

Instead of building the array first, we can loop through these indices and calculate the element's value and the required operations in the same step.

```java
class Solution {
    public int minOperations(int n) {
        int operations = 0;
        // The target value is n.
        // We only need to consider the elements in the first half of the array,
        // as they are the ones that need to be incremented.
        for (int i = 0; i < n / 2; i++) {
            int currentValue = (2 * i) + 1;
            operations += n - currentValue;
        }
        return operations;
    }
}
```
### Algorithm
*   Initialize a variable `operations` to 0.
*   The target value is `n`.
*   Iterate with a loop variable `i` from `0` to `n / 2 - 1`.
*   In each iteration, calculate the current element's value on the fly: `currentValue = (2 * i) + 1`.
*   Calculate the difference to the target: `diff = n - currentValue`.
*   Add this difference to the `operations` total.
*   After the loop finishes, return `operations`.

## Mathematical Formula (O(1) Solution)
The most efficient approach involves deriving a mathematical formula to calculate the result directly, without any iteration. By analyzing the pattern of operations, we can find a closed-form expression for the total number of operations.
**Time:** O(1) - The solution involves a fixed number of arithmetic operations, regardless of the value of `n`. · **Space:** O(1) - No extra space is required; the calculation is done in-place.
**Pros:** Extremely efficient with constant time and space complexity.; Provides a concise and elegant solution.
**Cons:** Requires mathematical insight to derive the formula, making it less obvious than iterative approaches.
### Explanation
As established, we need to calculate the sum of `(n - arr[i])` for `i` from `0` to `n / 2 - 1`. This sum is `S = Σ (n - (2*i + 1))` for `i` in `[0, n/2 - 1]`.

The terms we are summing form an arithmetic progression. For `n=6`, we sum `(6-1) + (6-3) + (6-5) = 5 + 3 + 1 = 9`. For `n=5`, we sum `(5-1) + (5-3) = 4 + 2 = 6`.

Let's analyze the sum based on whether `n` is even or odd.

*   **Case 1: `n` is even.** Let `n = 2k`. We sum `k` terms. The sum is `(2k-1) + (2k-3) + ... + 1`. This is the sum of the first `k` odd numbers, which is `k^2`. Since `k = n/2`, the result is `(n/2)^2 = n^2 / 4`.

*   **Case 2: `n` is odd.** Let `n = 2k+1`. We sum `k` terms. The sum is `(2k) + (2k-2) + ... + 2`. This is `2 * (k + (k-1) + ... + 1) = 2 * k(k+1)/2 = k(k+1)`. Since `k = (n-1)/2`, the result is `((n-1)/2) * ((n+1)/2) = (n^2 - 1) / 4`.

Interestingly, both cases can be unified. Using integer arithmetic, the expression `(n * n) / 4` gives the correct result for both even and odd `n`.

```java
class Solution {
    public int minOperations(int n) {
        // If n is even, n = 2k, result is k*k = (n/2)*(n/2) = n*n/4.
        // If n is odd, n = 2k+1, result is k*(k+1) = (n-1)/2 * (n+1)/2 = (n*n-1)/4.
        // Integer division n*n/4 handles both cases.
        return (n * n) / 4;
    }
}
```
### Algorithm
*   Given the input `n`.
*   Calculate `n * n`.
*   Perform integer division of the result by 4.
*   Return the final value.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int n) {
    int ans = 0;
    for (int i = 0; i < n >> 1; ++i) {
      ans += n - (i << 1 | 1);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperations(int n) {
    int ans = 0;
    for (int i = 0; i < n >> 1; ++i) {
      ans += n - (i << 1 | 1);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, n: int) -> int: return sum(n -
                                                       (i << 1 | 1) for i in range(n >> 1))

```