1551. Make all the minimum operations of all elements in the array

Thought：

It is the second question of the weekly match：6275Make all the minimum operations of all elements in the arrayII.md
The first edition of the heart of the heart。It’s completely different from the second edition，Originally wanted to practice the greedy algorithm。但是做着做着就发现了存在math规律。
Quote[yong]Big guy’s words：
Because it is the difference between the difference,很可能找到一个math公式,useO(1)Time complexity solution. Get a few simple examples first to find the rules

1. n=3 The minimum operation is 2
2. n=4 The minimum operation is 1 + 3
3. n=5 The minimum operation is 2 + 4
4. n=6 The minimum operation is 1 + 3 + 5
5. n=7 The minimum operation is 2 + 4 + 6
   whennWhen the number is,The minimum operation is1 + 3 + 5 + ... + n-1 = n*n/4
   whennWhen it is a strange number,The minimum operation is2 + 4 + ... + n-1 = (n*n - 1) / 4

Get this question,Feel a bit around,Careful analysis discovery arr[i] = (2 * i) + 1 (0 <= i < n)Is a typical equal number list(1,3,5,7,9...).
According to the formula of the equal number column,It’s easy to find a grouparrThe total element isn^2. In the question design, two bids are selected for each operationx ymakearr[x]minus onearr[y]plus one.
in other words,No matter how you choosex y,No matter how many times the operation,The sum of the array will not change. The design and guarantee that all elements in the array can ultimately be equal equal.
Then we assume that the final element is equal toaSon*a == n^2,soa == n,That is to say, the final array elements are alln.actuallynIs the average value of the array.
Know the end element is allnback,Start traversing in the middle by starting from the start and end of the array,You can reach the smallest number of operations.
Suppose the bidding on the left isi ((2 * i) + 1 < n)So相应右边的下标是n - i.
The corresponding two elemental values ​​andnThe difference isn - 1 + 2 * i.so我们只要计算数组中值小于nElements andnSummary of difference,Get the minimum operation number.

Code：

java

 int minOperations(int n) {
     return n * n / 4;
}
// Time and space complexity is all O(1)

java

 int minOperations(int n) {
    int operation = 0;
    for(int i = 1; i < n ; i += 2) {
        operation += (n - i);
    }
    return operation;
}
// Time complexity isO(n) Space complexity isO(1)

python

class Solution:
    def minOperations(self, n: int) -> int:
        operate = 0
        for i in range(1, n, 2):
            operate += (n - i)
        return operate

erlang

-spec min_operations(N :: integer()) -> integer().
min_operations(N) ->
N * N div 4.

dart

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

elixir

defmodule Solution do
  @spec min_operations(n :: integer) :: integer
  def min_operations(n) do
        div(n * n , 4)
  end
end