Formatted question description: https://leetcode.ca/all/1551.html

# 1551. Minimum Operations to Make Array Equal (Medium)

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 = 3Output:2Explanation: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 = 6Output:9

**Constraints:**

`1 <= n <= 10^4`

**Related Topics**:

Math

## Solution 1.

```
// OJ: https://leetcode.com/problems/minimum-operations-to-make-array-equal/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int minOperations(int n) {
int ans = 0;
for (int i = 0, j = n - 1; i < j; ++i, --j) {
int a = 2 * i + 1, b = 2 * j + 1;
ans += (b - a) / 2;
}
return ans;
}
};
```

We can simplify the code by removing constants.

```
// OJ: https://leetcode.com/problems/minimum-operations-to-make-array-equal/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int minOperations(int n) {
int ans = 0;
for (int i = 0, j = n - 1; i < j; ++i, --j) ans += j - i;
return ans;
}
};
```

## Solution 2.

Consider `[1,3,5,7,9]`

. The difference between `1`

and `9`

is `8`

, between `3`

, `7`

is `4`

. The answer is the sum of these differences divided by 2.

The largest difference is `2 * (n - 1) + 1`

minus `2 * 0 + 1`

which equals `2 * (n - 1)`

. The differences form a algorithmetic sequence whose constant difference is `4`

. So given the maximum value of the sequence is `mx = 2 * (n - 1)`

, there are `len = (mx + 3) / 4`

items in the sequence.

So the sum is `(mx + (mx - (len - 1) * 4)) * len / 2`

, and the answer is `(2 * mx - (len - 1) * 4) * len / 4`

.

```
// OJ: https://leetcode.com/problems/minimum-operations-to-make-array-equal/
// Time: O(1)
// Space: O(1)
class Solution {
public:
int minOperations(int n) {
int mx = 2 * (n - 1), len = (mx + 3) / 4;
return (2 * mx - (len - 1) * 4) * len / 4;
}
};
```

## Solution 3.

`n`

is the mean. The answer is `sum( n - 2 * i - 1 | 0 <= i < n / 2 )`

.

`sum ( n - 1 | 0 <= i < n / 2 ) = (n - 1) * floor(n / 2)`

.

`sum ( 2 * i | 0 <= i < n / 2 ) = (0 + 2 * (floor(n / 2) - 1)) * floor(n / 2) / 2 = (floor(n / 2) - 1) * floor(n / 2)`

Let `floor(n / 2) = k`

, then the total is `(n - 1) * k - (k - 1) * k = (n - k) * k`

.

So we can do

```
return (n - n / 2) * (n / 2);
```

Since `n - floor(n / 2)`

is `ceil(n / 2)`

, so the answer is also `ceil(n / 2) * floor(n / 2)`

. We can also do

```
return (n + 1) / 2 * (n / 2);
```

If `n`

is even, then `ceil(n/2) * floor(n/2) = n^2 /2`

.

If `n`

is odd, then `ceil(n/2) * floor(n/2) = (n + 1) / 2 * (n - 1) / 2 = (n^2-1) / 4 = floor(n^2 / 4)`

.

So in sum, we can do

```
return n * n / 4;
```

```
// OJ: https://leetcode.com/problems/minimum-operations-to-make-array-equal/
// Time: O(1)
// Space: O(1)
// Ref: https://leetcode.com/problems/minimum-operations-to-make-array-equal/discuss/794229/C%2B%2B-1-liner-O(1)-solution-(return-n*n4)-beats-100-with-detailed-explanation
class Solution {
public:
int minOperations(int n) {
return n * n / 4;
}
};
```

Java

```
class Solution {
public int minOperations(int n) {
int operations = 0;
for (int i = n - 1; i > 0; i -= 2)
operations += i;
return operations;
}
}
```