Skip to content

1551. Minimum Operations to Make Array Equal

SourceWeekly Contest 202 Q2DifficultyMediumRating1293

Description

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 <= 104

Solutions

Solution 1: Mathematics

Thinking

The array is \(1,3,5,\ldots,2n-1\). Each move increments one entry and decrements another until all values are equal. Simulating moves is wasteful for \(n\le 10^4\), and the sum is invariant, so the target is known.

The sum is \(n^2\), hence the common value is \(n\). Only the smaller half needs to grow: the \(i\)-th odd number \(2i+1\) lacks \(n-(2i+1)\). Summing those gaps is the minimum number of operations.

According to the problem description, the array \(arr\) is an arithmetic sequence with the first term as \(1\) and the common difference as \(2\). Therefore, the sum of the first \(n\) terms of the array is:

\[ \begin{aligned} S_n &= \frac{n}{2} \times (a_1 + a_n) \\ &= \frac{n}{2} \times (1 + (2n - 1)) \\ &= n^2 \end{aligned} \]

Since in one operation, one number is decreased by one and another number is increased by one, the sum of all elements in the array remains unchanged. Therefore, when all elements in the array are equal, the value of each element is \(S_n / n = n\). Hence, the minimum number of operations required to make all elements in the array equal is:

\[ \sum_{i=0}^{\frac{n}{2}} (n - (2i + 1)) \]

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

1
2
3
class Solution:
    def minOperations(self, n: int) -> int:
        return sum(n - (i << 1 | 1) for i in range(n >> 1))

1
2
3
4
5
6
7
8
9
class Solution {
    public int minOperations(int n) {
        int ans = 0;
        for (int i = 0; i < n >> 1; ++i) {
            ans += n - (i << 1 | 1);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int minOperations(int n) {
        int ans = 0;
        for (int i = 0; i < n >> 1; ++i) {
            ans += n - (i << 1 | 1);
        }
        return ans;
    }
};

1
2
3
4
5
6
func minOperations(n int) (ans int) {
    for i := 0; i < n>>1; i++ {
        ans += n - (i<<1 | 1)
    }
    return
}

1
2
3
4
5
6
7
function minOperations(n: number): number {
    let ans = 0;
    for (let i = 0; i < n >> 1; ++i) {
        ans += n - ((i << 1) | 1);
    }
    return ans;
}

Comments