# LeetCode - Minimum Operations to Make Array Equal

### **Problem statement**

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

Problem statement taken from: [https://leetcode.com/problems/minimum-operations-to-make-array-equal](https://leetcode.com/problems/minimum-operations-to-make-array-equal)

**Example 1:**

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

```plaintext
Input: n = 6
Output: 9
```

**Constraints:**

```plaintext
- 1 <= n <= 10^4
```

### **Explanation**

#### **Brute Force**

As per the problem statement, the value at index `i` in the array is equal to `(2 * i) + 1`. The array of size n can be represented as follows:

```plaintext
arr = [2 * 0 + 1, 2 * 1 + 1, 2 * 2 + 1,.... 2 * (n - 1) + 1]

when n = 6
arr = [2 * 0 + 1, 2 * 1 + 1, 2 * 2 + 1, 2 * 3 + 1, 2 * 4 + 1, 2 * 5 + 1]
    = [1, 3, 5, 7, 9, 11]

when n = 7
arr = [1, 3, 5, 7, 9, 11, 13]
```

The array elements are ordered in a linear arithmetic series. Let's calculate the number of operations at each step.

```plaintext
arr = [1, 3, 5, 7, 9, 11, 13]

First operation, we will increase arr[0] = 1 by 1 and decrease arr[6] = 13 by 1.
arr = [2, 3, 5, 7, 9, 11, 12]

We repeat the above process till arr[0] and arr[6] = 7

Number of operations = 6

Similarly, for arr[1] and arr[5], the number of operations to update value to 7 will be 4.
For arr[2] and arr[4], the number of operations will be 2.

Total number of operations = 6 + 4 + 2
                           = 12

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]

First operation, we will increase arr[0] = 1 by 1 and decrease arr[8] = 17 by 1.
arr = [2, 3, 5, 7, 9, 11, 13, 15, 16]

We repeat the above process till arr[0] and arr[8] = 9

Number of operations = 8

Similarly, for arr[1] and arr[7], the number of operations to update the value to 9 will be 6.
For arr[2] and arr[6], the number of operations will be 4.
For arr[3] and arr[5], the number of operations will be 2.

Total number of operations = 8 + 6 + 4 + 2
                           = 20
```

From the above pattern, we observe at any step or index `i`, the number of operations is `n - 2 * i - 1`. The total number of operations will be

```plaintext
number_of_operations = 0

for(int i = 0; i < n / 2; i++) {
    number_of_operations += n - (2 * i) - 1
}

return number_of_operations
```

The time complexity of the above approach is **O(n)**, and the space complexity is **O(1)**.

#### **Efficient approach**

We can further optimize the above approach. Let's observe the pattern for the number of operations. For every i = 0, 1, 2,...(n/2) - 1, we get the series as

```plaintext
n - 1, n - 3, n - 5,.......7, 5, 3, 1.
```

This is an arithmetic series `a, a + d, a + 2d....`, where a = 1 and d = 2. The arithmetic sum of this series is

```plaintext
sum = n * (2 * a + (n - 1) * d) / 2
```

In our case, n = n / 2. We apply the above formula

```plaintext
sum = (n / 2) * (2 * 1 + (n/2 - 1) * 2) / 2
    = n * (2 + (n - 2)) / 4
    = n * (n) / 4
    = (n * n) / 4
```

When n is odd, the arithmetic series is `n - 1, n - 3,....5, 3, 1`. When n is even, the arithmetic series is `n - 1,...6, 4, 2`. We apply the same arithmetic series formula, reducing the sum to `(n * n) / 4`.

The time and space complexity of the above approach is **O(1)**.

Let's check our algorithm in **C++**, **Golang**, and **JavaScript**.

#### **C++ solution**

```cpp
class Solution {
public:
    int minOperations(int n) {
        return (n * n) >> 2;
    }
};
```

#### **Golang solution**

```go
func minOperations(n int) int {
    return (n * n) >> 2
}
```

#### **JavaScript solution**

```javascript
var minOperations = function(n) {
    return (n * n) >> 2;
};
```

For n = 6, we return the solution as (6 \* 6) &gt;&gt; 2 = 9.