问题描述
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
问题分析
根据问题描述，每次都是选择2个元素，一加一减；那么显然，所有元素向数组平均值逼近，差距是最小的；
我们可以先计算出数据平均值，然后针对小于平均值的元素，依次累加与平均值的差额即为最终所求。
示例代码
func minOperations(n int) int {
ans := 0
avg := (1 + (2*(n-1) + 1)) / 2
start := avg - 1
for i := 0; i < n/2; i++ {
ans += start
start -= 2
}
return ans
}