This article has participated in the Denver Nuggets Creators Camp 3 “More Productive writing” track, see details: Digg project | creators Camp 3 ongoing, “write” personal impact

describe

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].
Copy the code

Example 2:

Input: n = 6
Output: 9
Copy the code

Note:

1 <= n <= 10^4
Copy the code

parsing

Arr [I] = (2 * I) + 1; arr[I] = (2 * I) + 1; arr[y] = (2 * I) + 1; How many operations can I do to get an ARR that has the same elements. In fact, this kind of questions are generally to find the rule of the question, next I give you find:

  • When n = 1, arr=[1], since the elements are all equal, no operation is required and 0 is returned

  • When n = 2 and arr=[1,3], only one operation is required to obtain [2,2], which directly returns 1

  • When n = 3, arr=[1,3,5], perform the following operation, get [3,3,3], directly return 2

    (2 and 4] filling [3]Copy the code

  • When n = 4, arr=[1,3,5,7], perform the following operation, get [4,4,4,4], directly return 4

    ,3,5,5,3,5,6 [2] [3] [4,3,5,4],4,4,4 [4]Copy the code

  • When n = 5, arr=[1,3,5,7,9], perform the following operation to get [5,5,5,5], and directly return 6

    ,3,5,7,7,3,5,7,8 [2] [3],3,5,7,6 [4] [5,3,5,7,5],4,5,6,5 [5],5,5,5,5 [5]Copy the code

  • When n = 6 and arr=[1,3,5,7,9,11], perform the following operation to get [6,6,6,6,6,6] and return 9 directly

    ,3,5,7,9,9,3,5,7,9,10 [2] [3] [4,3,5,7,9,8],3,5,7,9,7 [5] [6,3,5,7,9,6],4,5,7,8,6 [6],5,5,7,7,6 [6],6,5,7,6,6 [6] ,6,6,6,6,6 [6]Copy the code

We’ve already seen the pattern:

  • When you give n, you end up with all the equal elements of arr being n
  • Because if you add one to the first element, you subtract one from the next element, so you just add up the number of times you increase each element to n for the first half of the elements

answer

class Solution(object):
    def minOperations(self, n):
        """
        :type n: int
        :rtype: int
        """
        result = 0
        for i in range(1,n+1,2):
            result += n-i
        return result
        	      
		
Copy the code

The results

Runtime: 77 ms, faster than 30.60% of Python online submissions for Minimum Operations to Make Array Equal. Memory Usage: Submissions in the Python online list for Minimum Operations to Make Array Equal.Copy the code

Original link: leetcode.com/problems/mi…

Your support is my biggest motivation