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

Difficulty: interview

Starter code:

class Solution:
    def minOperations(self, n: int) -> int:
        

Solutions:
class Solution:
    def minOperations(self, n: int) -> int:
        return (n*n)>>2
                


class Solution:
    def minOperations(self, n: int) -> int:
        if n % 2 == 0:
            return (n//2)*(n//2)
        else:
            return (n-1)*(1+(n-1)//2)//2

class Solution:
    def minOperations(self, n: int) -> int:
        out = 0
        diff = (n - 1)
        while diff > 0:
            out += diff
            diff -= 2
        
        return out


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

class Solution:
    def minOperations(self, n: int) -> int:
        sum_out = None    
        if n%2 == 1:
            l = int(n/2)
            num_ops = n-1
            sum_out = 0
            for i in range(l):
                sum_out += num_ops
                num_ops -=2
                
        elif n%2 == 0:
            num_ops = n-1;
            l = int(n/2)
            sum_out = 0
            for i in range(l):
                sum_out+= num_ops
                num_ops -=2 
                
        return sum_out        
        
                


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

class Solution:
    def minOperations(self, n: int) -> int:
        avg = n
        
        count = 0
        # print(\"n = {}\".format(n))
        for i in range((n//2)):
            count += avg - (2*i + 1)
            # print(\"i = {}, count = {}\".format(i, count))
          
        return count


class Solution:
    def minOperations(self, n: int) -> int:
        total = 0
        for i in range(n//2): 
            total += n - (2*i + 1)
        return total
    
        # middle one is 2k + 1
        # first is 2*0 + 1
        # last is 2*n + 1 --> diff is 2(n-k) so around n
        # second last is 2*(n-1) + 1 --> diff is 2(n-k-1) so around n - 2
        # inds_from_end = 0
        # arr = [(2*i)+1 for i in range(n)]
        # count = 0
        # # print(arr)
        # while len(set(arr)) != 1 and inds_from_end < n//2:
        #     # print(arr, n-inds_from_end-1)
        #     while arr[inds_from_end] != arr[n-inds_from_end-1]:
        #         print(arr, count)
        #         arr[inds_from_end] += 1
        #         arr[n-inds_from_end-1] -= 1
        #         count += 1
        #     inds_from_end += 1
            
        return count

class Solution:
    def minOperations(self, n: int) -> int:
        if n == 1:
            return 0
        result = 0
        for i in range(n//2):
            if n % 2 != 0:
                result += 2*(i+1)
            else:
                result += 1+ 2*i
        return result
    
        


class Solution:
    def minOperations(self, n: int) -> int:
        count = sum([x*2 for x in range((n+1)//2)])
        if n % 2 == 0:
            count += n//2
        return count

class Solution:
    def minOperations(self, n: int) -> int:
        i, ans = 1, 0
        while i < n:
            ans += n - i
            i += 2
        return ans

class Solution:
    def minOperations(self, n: int) -> int:
        l, r = 1, 2*(n-1) + 1
        total = 0
        
        while l < r:
            total += (r-l) // 2
            l += 2
            r -= 2
        
        return total

class Solution:
    def minOperations(self, n: int) -> int:
        return n**2 // 4

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

class Solution:
    def minOperations(self, n: int) -> int:
        count = 0
        if n % 2 == 1:
            i = 0
            mid = (2*(int(n/2)))+1
            while i < int(n/2):
                count += mid-((2*i)+1)
                i+=1
        else:
            i = 0
#             [1, 3, 5, 7, 9, 11]
            mid = (2*((n/2)))
            while i < n/2-1:
                count += mid-((2*i)+1)
                i +=1
            count += 1
        return int(count)
    


class Solution:
    def minOperations(self, n: int) -> int:
        mid=0
        count=0
        if n%2 == 0:
            mid = ((n//2)*2+1 + (n//2-1)*2 +1)//2
            for i in range(n//2):
                count=count + mid-(i*2+1) 
                
        else:
            mid = ((n-1)//2)*2 +1
            for i in range(n//2):
                count=count + mid-(i*2+1) 
                
                
        return count

# [1, 3, 5, 7, ...]

# [1, 3, 5, 7, 9] -> 5 will be the mid point

# if n is odd -> 
#   for i->n/2
#       steps += 2**i

# We have to take advante of the symmetry

# if n is even
# [1, 3, 5, 7] -> Mid point is 4
#  

# [1,3,5,7,9.11]
class Solution:
    def minOperations(self, n: int) -> int:
        mid_point = (2*(n//2)) + 1 - (n%2==0)
        return sum([ mid_point - ((2*i)+1) for i in range(n//2)] )
        
        
            


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

class Solution:
    def minOperations(self, n: int) -> int:
        count = 0
        if n % 2 == 1:
            i = 0
            mid = (2*(int(n/2)))+1
            # print(mid)
            # print(int(n/2))
            while i < int(n/2):
                # print(i)
                count += mid-((2*i)+1)
                i+=1
        else:
            i = 0
#             [1, 3, 5, 7, 9, 11]
            mid = (2*((n/2)))
            # print(mid)
            while i < n/2-1:
                # print(i)
                # print(count)
                count += mid-((2*i)+1)
                i +=1
            count += 1
        return int(count)
    


class Solution:
    def minOperations(self, n: int) -> int:
        even = n % 2 == 0 and True or False
        half = even and int(n/2) or n//2
        left = right = 0
        for i in range(n):
            if i < half:
                left += (2*i)+1
            elif i == half and even:
                return left
            elif i > half:
                right += (2*i)+1
    
        return int((right - left) / 2)

class Solution:
    def minOperations(self, n: int) -> int:
        # array is like 1, 3, 5, 7, 9....
        #               2     5     8
        #               3           7
        #               4           6
        #               5           5
        
        # 2 6 3 5 4 4
        # diff / 2
        # array is like 1 3 5 7
        #                      
        if n == 1:
            return 0

        # one pair is difference divided by 2
        low = 0
        hi = n - 1
        num_ops = 0
        while low < hi:
            min_num = (2 * low) + 1
            max_num = (2 * hi) + 1

            num_ops += (max_num - min_num) // 2
                
            low += 1
            hi -= 1
            
        return num_ops

class Solution:
    def minOperations(self, n: int) -> int:
        arr = [ i for i in range(1, n*2, 2) ]
        target = 0
        ops = 0

        if n%2 == 1:
                idx = n//2
                target = arr[idx]

        else:
            right = n//2
            left = right-1
            print(right)
            print(left)
            print(arr)
            target = arr[left]+1

        for j in range(n//2):
            diff = target - arr[j]
            ops += diff

        return ops


class Solution:
    def minOperations(self, n: int) -> int:
        # arr = []
        # for i in range(0, n):
        #     arr.append(2*i+1)
        sumz = 0
        for i in range(0, n):
            sumz+=2*i+1
        median = sumz//n 
        # print(median, arr)
        steps = 0
        for i in range(n//2):
            steps+=median-(2*i+1)

        return steps 

class Solution:
    def minOperations(self, n: int) -> int:
        if n%2 == 0:
            return int((n/2)**2)
        else:
            return int(((n-1)/2)**2 + (n-1)/2)

class Solution:
    def minOperations(self, n: int) -> int:
        arr = [2 * i + 1 for i in range(n)]
        target = sum(arr)//n
        ans = 0
        for i in range(n//2):
            ans += target - arr[i]
        return ans


class Solution:
    def minOperations(self, n: int) -> int:
        
        ops = 0
        for i in range(n):
            ops += abs((2 * i + 1) - n)
        
        return ops // 2
#         (1 + n) / 2 * n * 2 + n
        
#         n2 + n + 1
        
#         (n - 1)
        
        
#         1 + 2n - 2 + 1 / 2 * n
        
        
#         n^2 / n


class Solution:
    def minOperations(self, n: int) -> int:
        
        
        sum_tot = 0
        for i in range(n):
            val = 2*i+1
            #print(val)
            if val > n:
                sum_tot += val-n
            else:
                sum_tot += n - val
        
        return(int(sum_tot/2))
        
        
        '''
        if n%2  == 0:
            median = int((arr[int(n/2)] + arr[int(n/2)-1])/2)
        else:
            median = arr[int(n/2)]
        print(median)
        
        ctr = 0
        while(len(set(arr)) > 1):
            min_elem = arr[-1] + 1
            max_elem = -1
            min_ind = -1
            max_ind = -1
            for i in range(len(arr)):
                if arr[i] > max_elem:
                    max_elem = arr[i]
                    max_ind = i
                if arr[i] < min_elem:
                    min_elem = arr[i]
                    min_ind = i
            arr[max_ind] -= 1
            arr[min_ind] += 1
            ctr += 1
        
        return ctr
        '''

class Solution:
    def minOperations(self, n: int) -> int:
        # 평균을 구한다. 평균은 n이 된다.
        # 평균으로 부터 각 거리를 다 더한다.
        # 반으로 나눈다.
        count=0;
        for i in range(n):
            target=(2*i)+1;
            count+=abs(n-target);
        print(count);
        return count//2;


class Solution:
    def minOperations(self, n: int) -> int:
        arr = [2 * i + 1 for i in range(n)]
        
        target = sum(arr)//n
        ans = 0
        for i in range(len(arr)//2):
            ans += abs(arr[i] - target)
        return ans

class Solution:
    def minOperations(self, n: int) -> int:
        arr = [2 * i + 1 for i in range(n)]
        
        target = sum(arr)//n
        res = 0
        for i in range(n//2):
            res += abs(target - arr[i])
        return res


class Solution:
    def minOperations(self, n: int) -> int:
        totalSum = int(n*(2*1+(n-1)*2)/2)
        #numbers are of the sequence = 1,3,5,7,....
        targetNumber = int(totalSum/n)
        #so each number is (targetNumber-i)
        return sum(abs(2*i+1-targetNumber) for i in range(0,n))//2


class Solution:
    def minOperations(self, n: int) -> int:
        arr = [2 * i + 1 for i in range(n)]
        target = sum(arr)//n
        ans = 0
        for i in range(n//2):
            ans += abs(target - arr[i])
        return ans


class Solution:
    def minOperations(self, n: int) -> int:
        arr=[]
        c=0
        for i in range(n):
            arr.append(2*i+1)
        tar1=len(arr)
        tar2=tar1
        if(tar1%2==0):
            tar2=tar2-1
        ans=arr.index(tar2)
        for i in range(ans):
            c+=tar1-arr[i]
        if(tar1!=tar2):
            c+=1
        return c

class Solution:
    def minOperations(self, n: int) -> int:
        arr = []
        min_operations = 0
        for i in range(n):
            arr.append((2 * i) + 1)
        target = sum(arr) // n
        middle = ceil(n / 2)
        # print(arr, target, middle)
        for i in range(ceil(n / 2)):
            min_operations += (target - arr[i])
        return min_operations
    
# 1 - 0
# 2 - 1
# 3 - 2
# 4 - 4
# 5 - 6
# 6 - 9


class Solution:
    def minOperations(self, n: int) -> int:
        if n%2==0:
            return int(n/2)*int(n/2)
        else:
            return int(n/2)*(int(n/2)+1)


import math
class Solution:
    def minOperations(self, n: int) -> int:
        ans = 0
        for x in range(0, n+1):
            ans += math.floor(x/2)
        return ans

class Solution:
    def minOperations(self, n: int) -> int:
        nums = [2 * i + 1 for i in range(n)]
        res = 0
        for i in range(n // 2):
            res += (nums[n - 1 - i] - nums[i]) >> 1
        return res

class Solution:
    def minOperations(self, n: int) -> int:
        if n == 1:
            return 0
        elif n == 2:
            return 1
        else:
            arr = [0]*n
            arr[0] = 1
            arr[1] = 3
            for i in range(2,n):
                arr[i] = arr[i-1] + 2
            if n % 2 != 0:
                ans = 0
                i = 0
                j = len(arr)-1
                while i < j:
                    ans += (arr[j]-arr[i])//2
                    i += 1
                    j -= 1
                return ans
            else:
                ans = 0
                n = n // 2
                i = 1
                count = 0
                ans = 0
                while count < n:
                    ans += i
                    i += 2
                    count += 1
                return ans

class Solution:
    def minOperations(self, n: int) -> int:
        arr=[]
        for i in range(n):
            arr.append((2*i)+1)
        s=sum(arr)//n
        res=0
        for i in range(n//2):
            res+=s-arr[i]
        return res

class Solution:
    def minOperations(self, n: int) -> int:
        A = [2*i+1 for i in range(n)]
        median = A[len(A)//2]
        return sum(abs(i - median) for i in A)//2


import numpy as np
class Solution:
    def minOperations(self, n: int) -> int:
        res = 0
        for i in range(n):
            value = 2*i+1-n
            if value>0:
                res+= value
        return res

class Solution:
    def minOperations(self, n: int) -> int:
        arr = [0] * n
        for i in range(len(arr)):
            arr[i] = (2 * i) + 1
        s = 0
        for i in range(len(arr)//2):
            s += abs(arr[i] - arr[len(arr)-i-1])
        return s//2            

class Solution:
    def minOperations(self, n: int) -> int:
        s = 0
        for i in range(n):
            s = s + 2*i+1
        x = s//n
        print(x)
        y = 0
        for i in range(n):
            if(2*i+1<x):
                y = y+x-(2*i+1)
        return y
            
            
        
        


class Solution:
    def minOperations(self, n: int) -> int:
        half = n//2
        return half*n - half**2

class Solution:
    def minOperations(self, n: int) -> int:
        arr = [2 * i + 1 for i in range(n)]
        
        target = sum(arr)//n
        ans = 0
        for i in range(n//2):
            ans += abs(target - arr[i])
        return ans


class Solution:
    def minOperations(self, n: int) -> int:
        arr = [(2 * i) + 1 for i in range(n)]
        target = sum(arr) / n
        opCount = 0
        ptr1 = 0
        ptr2 = len(arr) - 1
            
        while ptr1 < ptr2:
            stepSum = (arr[ptr2] - arr[ptr1]) // 2
            opCount += int(stepSum)
            ptr1 += 1
            ptr2 -= 1
        
        return opCount
            


class Solution:
    def minOperations(self, n: int) -> int:
        arr = [2*i+1 for i in range(n)]
        each = sum(arr)//n
    
        for i in range(n):
            arr[i] = each - arr[i]
        sums = 0
        for i in arr:
            if i>0:
                sums += i
        return sums
                

            


class Solution:
    def minOperations(self, n):
        arr = [];
        count = 0;

        for x in range(n):
            arr.append(2 * x + 1)
        avg = sum(arr) // n

        for x in range(n):
            count += abs(arr[x] - avg)
        return count // 2

sol = Solution();
x = sol.minOperations(3);
print(x);

class Solution:
    def minOperations(self, n: int) -> int:
        #if n is odd, the middle one does not need an operatio
        #[1,3,5,10,17,26,(37)]
        A = [x*2+1 for x in range(n)]
        s = sum(A)/n
        c = 0
        while True:
            for i in A:
                if i>=s:
                    return int(c)
                c += (s-i)


class Solution:
    def minOperations(self, n: int) -> int:
        if n==1:
            return 0
        elif n==2:
            return 1
        else:
            count=0
            i=1
            while i<n:
                print(i)
                count+=n-i
                i+=2
            return count

class Solution:
    def minOperations(self, n: int) -> int:
        ans=0
        tot=0
        arr=[]
        for i in range(n):
            arr.append((2*i)+1)
            tot+=((2*i)+1)
        tot=tot//n
        for i in arr:
            if(i<tot):
                ans+=(tot-i)
        return ans

class Solution:
    def minOperations(self, n: int) -> int:
        if n==1:
            return 0
        elif n==2:
            return 1
        else:
            target=n+1
            count=0
            i=1
            while i<=n:
                count+=abs(target-2*i+1)
                i+=1
            return count//2

class Solution:
    def minOperations(self, n: int) -> int:
        return (n//2)*((n//2)+n%2)

class Solution:
    def minOperations(self, n: int) -> int:
        arr = []
        for i in range(n):
            arr.append(2*i+1)
            
        double_cnt = 0
        for i in range(len(arr)):
            double_cnt += abs(arr[i]-n)
        return double_cnt//2
            


class Solution:
    def minOperations(self, n: int) -> int:
        A = [_*2 + 1 for _ in range(n)]
        ret = 0
        for i in range(0, n //2):
            ret += n - i * 2 - 1
        return ret

class Solution:
    def minOperations(self, n: int) -> int:
        # tot=0
        # quant = 0
        # for i in range(n):
        #     quant = abs(n - (2*i+1))
        #     if( quant> 0):
        #         tot +=  quant
        
        return sum([abs(n-2*i-1)  for i in range(n) if abs(n-2*i-1) > 0]) // (2)
            
            
            
        
            
        
            
            


import numpy as np
class Solution:
    def minOperations(self, n: int) -> int:
        res = np.zeros((n,1),dtype=int)
        for i in range(n):
            value = 2*i+1-n
            if value>0:
                res[i] = value
        return res.sum()

class Solution:
    def minOperations(self, n: int) -> int:
        
        total = 0
        arr = []
        
        for i in range(n):
            arr.append(2*i + 1)
        
        for i in range(int(len(arr)/2)):
            total += (arr[int(math.ceil(len(arr)/2 + i))] - arr[i]) / 2
        
        return int(total)
        
        


class Solution:
    def minOperations(self, n: int) -> int:
        
        def isAllEqual(array):
            for i in range(len(array[1:])):
                if array[i] != array[0]:
                    return False
            
            return True
        
        # generate array; where array[i] = 2i + 1
        arr = [((2 * x)+1) for x in range(n)]
        
        # choose x and y, arr[x]-=1 arr[y]-=1
        # generate all pairs
        count = 0
        x = 0
        y = len(arr)-1
        
        while (x < y):
            diff = int((arr[y]-arr[x])/2)
            arr[x] += diff
            arr[y] -= diff
            count += diff
            x += 1
            y -= 1
        
        return count


class Solution:
    def minOperations(self, n: int) -> int:
        
        generatedArray = []
        
        for i in range(n):
            generatedArray.append((2 * i) + 1)

        arrayLength = len(generatedArray)

        noOperations = 0
        
        # if arrayLength % 2 != 0:
        #     targetNumber = generatedArray[int(arrayLength // 2)]
        # else:
        #     targetNumber = generatedArray[int(arrayLength // 2) - 1] + 1 
            
        for i in range(int(arrayLength//2)):
            noOperations += (n - generatedArray[i]) 

        return noOperations

class Solution:
    def minOperations(self, n: int) -> int:
        res = 0
        arr = [2*i+1 for i in range(n)]
        for item in arr:
            if item <n:
                res+=n-item
            else:
                break
        return res


class Solution:
    def minOperations(self, n: int) -> int:
        sum=0
        for i in range(n):
            sum +=2*i+1
        eq=sum/n

        step=0
        for i in range(int(n/2)):
            step +=int(eq-(2*i+1))
        return step

class Solution:
    def minOperations(self, n: int) -> int:
        return sum(list(range(1, n, 2))) if n%2 == 0 else sum(list(range(2, n, 2)))

class Solution:
    def minOperations(self, n: int) -> int:
        arr = [i * 2 + 1 for i in range(n)]
        if n % 2 == 0:
            median = (arr[len(arr) // 2] + arr[(len(arr) // 2) - 1]) // 2
            return sum(arr[i] - median for i in range(n // 2 + 1, n)) + 1
        else:
            median = arr[len(arr) // 2]
            return sum(arr[i] - median for i in range(n // 2 + 1, n))

class Solution:
    def minOperations(self, n: int) -> int:
        arr = [2*i+1 for i in range(n)]
        avg = int(sum(arr) / len(arr))
        return sum([abs(a-avg) for a in arr])//2

class Solution:
    def minOperations(self, n: int) -> int:
        
        v = 0
        for i in range(n): v += 2 * i + 1
        
        mean = v // n
        
        ans = 0
        for i in range(n):
            ans += max(0, 2 * i + 1 - mean)
        return ans

class Solution:
    def minOperations(self, n: int) -> int:
        arr=[0]*n
        for i in range(n):
            arr[i]=(2*i)+1
        print(arr)
        
        k=arr[int(len(arr)/2)]
        print(k)
        total=0
        for i in range(len(arr)):
            p=int(arr[i])
            total=total+abs(k-p)
        return int(total/2)

class Solution:
    def minOperations(self, n: int) -> int:
        if n == 0 or n == 1:
            return 0
        else:
            return (int(n/2)) + self.minOperations(n-1)

class Solution:
    def minOperations(self, n: int) -> int:
        # [1] 1 => 0
        # [1,3] 2 => 1
        # [1,3,5] 3 => 2
        # [1,3,5,7] 4 => 1 + 3 = 4
        # [1,3,5,7,9] 5 => 2 + 4 = 6
        # [1,3,5,7,9,11] 6 => 1 + 3 + 5 = 9
        # [1,3,5,7,9,11,13] 7 => 2 + 4 + 6 = 12
        
        if n <= 1:
            return 0
        else:
            ops = 0
            for x in range(n-1,0, -2):
                ops += x
            return ops
            
            
        


class Solution:
    def minOperations(self, n: int) -> int:
        half = n//2
        half_list = [x for x in range(1,n,2)]
        return half*n - sum(half_list)