[LeetCode April Challange] Day 06 - Minimum Operations to Make Array Equal

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 <= 10^4

---

Solution

Time complexity : O(1)
Space complexity : O(1)

class Solution {
public:
    int minOperations(int n) {
        return n*n/4;
    }
};

target = sum([1, 3, 5, …, 2n-1]/n) = [(1+(2n-1))*n/2]/n = n
可以用平衡的加減法當作一個動作，
例：1, 3, 5, 7, target = n = 4
則 1加1(7減1) 做 3 次，3加1(5減1) 做 1 次，即可達到平衡。

因此所需的動作次數，為 (4-1)+(4-3) = 4。

一般化則為 (n-1)+(n-3)+…+1(or0)。

再利用等差級數和公式可得：1+3+…+(n-1) = (1+(n-1)) * n/2 / 2 = n^2 / 4;