LeetCode 1551. Minimum operand to make all elements in the array equal

1551. The minimum operands that make all elements in an array equal

There is a length of n Array of arr , among arr[i] = (2 * i) + 1 （ 0 <= i < n ）.

In one operation , You can choose two subscripts , Write it down as x and y （ 0 <= x, y < n ） And make arr[x] subtract 1 、arr[y] add 1 （ namely arr[x] -=1 And arr[y] += 1 ）. The ultimate goal is to make all elements in the array equal . The title test case will Guarantee ： After several steps , All elements in the array can eventually be equal .

Give you an integer n, That's the length of the array . Please return the array arr Required for all elements to be equal Minimum operands .

Example 1：

 Input ：n = 3
 Output ：2
 explain ：arr = [1, 3, 5]
 Select... For the first operation  x = 2  and  y = 0, Make array  [2, 3, 4]
 The second operation continues  x = 2  and  y = 0, The array will become  [3, 3, 3]

Example 2：

 Input ：n = 6
 Output ：9

Tips ：

• 1 <= n <= 10^4

Two 、 Method 1

greedy

class Solution {
    
    public int minOperations(int n) {
    
        int res = 0;
        for (int i = 0; i < n; i++) {
    
            int x = (2 * i) + 1;
            if (x > n) {
    
                res += x - n;
            }
        }
        return res;
    }
}

Complexity analysis

• Time complexity ：O(n).

• Spatial complexity ：O(1).

3、 ... and 、 Method 2

mathematics

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

Complexity analysis

• Time complexity ：O(1).

• Spatial complexity ：O(1).