1551. Minimum Operations to Make Array Equal #
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 <= 10^4
Problem Summary #
There is an array arr of length n, where arr[i] = (2 * i) + 1 (0 <= i < n). In one operation, you can choose two indices, denoted as x and y (0 <= x, y < n), and subtract 1 from arr[x] and add 1 to arr[y] (i.e., arr[x] -=1 and arr[y] += 1). The final goal is to make all elements in the array equal. The test cases will guarantee that after performing several operations, all elements in the array can eventually become equal. Given an integer n, the length of the array. Return the minimum number of operations required to make all elements in array arr equal.
Solution Approach #
This is a math problem. The operation given in the problem does not change the sum of all elements in the array. If all elements are eventually made equal, then the average value of all elements in the array is the value of each element in the final array. The strategy for the minimum number of operations should be centered around the average: numbers to the right of the center decrease, and the symmetric numbers to the left of the center increase. Since the original array is an arithmetic sequence with a difference of 2 between each pair of adjacent elements, the number of operations can be calculated using mathematical methods.
Discuss separately based on whether the array length is odd or even. If the array length is odd, the required number of operations is:
\[ \begin{aligned} &\quad 2 + 4 + \cdots + 2\cdot\left\lfloor\frac{n}{2}\right\rfloor \\ &= \frac{1}{2}\left\lfloor\frac{n}{2}\right\rfloor\left(2\cdot\left\lfloor\frac{n}{2}\right\rfloor + 2\right) \\ &= \left\lfloor\frac{n}{2}\right\rfloor \left(\left\lfloor\frac{n}{2}\right\rfloor + 1\right) \\ &= \frac{n-1}{2}\left(\frac{n-1}{2} + 1\right) \\ &= \frac{n-1}{2}\cdot\frac{n+1}{2} \\ &= \frac{n^2-1}{4} \\ &= \left\lfloor\frac{n^2}{4}\right\rfloor \end{aligned} \]If the array length is even, the required number of operations is:
\[ \begin{aligned} &\quad 1 + 3 + \cdots + \left(2\cdot\left\lfloor\frac{n}{2}\right\rfloor - 1\right) \\ &= \frac{1}{2}\left\lfloor\frac{n}{2}\right\rfloor\left(2\cdot\left\lfloor\frac{n}{2}\right\rfloor - 1 + 1\right)\\ &= \left(\left\lfloor\frac{n}{2}\right\rfloor\right)^2 \\ &= \frac{n^2}{4} \end{aligned} \]In summary, the minimum number of operations is n^2/4
Code #
package leetcode
func minOperations(n int) int {
return n * n / 4
}
中文