1551. Minimum Operations to Make Array Equal

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

Related Topics:
Math

Solution 1.

// OJ: https://leetcode.com/problems/minimum-operations-to-make-array-equal/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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;
    }
};