Given an array of N integers arr[ ], the task is to count the minimum number of operations to equalize the array i.e. to make all array elements equal.
In one operation, you can choose two elements arr[i] and arr[j] such that arr[i] > arr[j] and change them to arr[i] = arr[i] - 1 and arr[j] = arr[j] + 1.
If it is impossible to equalize the array print "-1".
Example 1:
Input:
N = 5
arr[] = {1, 3, 2, 0, 4}
Output:  3
Explanation: We can equalize the array by 
making value of all elements equal to 2. 
To achieve this we need to do minimum 3 
operations:
1. arr[0]++ and arr[1]--
2. arr[3]++ and arr[4]--
3. arr[3]++ and arr[4]--
Example 2:
Input:
N = 3
arr[] = {1, 7, 1}
Output:  4
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function minOperations() that takes array arr[ ] and integer N as input parameters and returns the required answer.
Note - return -1, if it is not possible to equalize the array.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:
    def findDifference(self,arr,N):
        #Code here


Solutions:
class Solution:

	def findDifference(self, arr, N):
		s = sum(arr)
		if s % N != 0:
			return -1
		ds = 0
		e = s / n
		for i in range(n):
			ds += abs(arr[i] - e)
		return int(ds / 2)


class Solution:

	def findDifference(self, arr, N):
		s = 0
		for i in range(N):
			s += arr[i]
		if s % N == 0:
			count = 0
			for i in range(N):
				if arr[i] != s // N:
					count += abs(arr[i] - s // N)
			return count // 2
		return -1


class Solution:

	def findDifference(self, arr, N):
		target = sum(arr) / N
		if target != int(target):
			return -1
		target = int(target)
		count = 0
		for item in arr:
			count += abs(target - item)
		return count // 2


class Solution:

	def findDifference(self, arr, n):
		sum = 0
		for i in range(0, n):
			sum += arr[i]
		if sum % n != 0:
			return -1
		diff_sum = 0
		eq = sum / n
		for i in range(0, n):
			diff_sum += abs(arr[i] - eq)
		return int(diff_sum / 2)


class Solution:

	def findDifference(self, arr, N):
		s = sum(arr)
		if s % N != 0:
			return -1
		mean = s // N
		return sum([abs(elem - mean) for elem in arr]) // 2


class Solution:

	def findDifference(self, arr, N):
		diff = 0
		sums = 0
		average = sum(arr) // N
		for i in range(N):
			if arr[i] < average:
				sums += average - arr[i]
			elif arr[i] > average:
				diff += arr[i] - average
		if sums == diff:
			return sums
		else:
			return -1


class Solution:

	def findDifference(self, arr, n):
		sum = 0
		av = 0
		for i in range(n):
			sum += arr[i]
		cnt = 0
		av = sum // n
		if sum != av * n:
			return -1
		for j in range(n):
			if arr[j] < av:
				cnt += av - arr[j]
		return cnt


class Solution:

	def findDifference(self, arr, N):
		k = sum(arr)
		if k % N != 0:
			return -1
		else:
			dif = 0
			m = k // N
			for i in arr:
				dif += abs(m - i)
			return dif // 2


class Solution:

	def findDifference(self, arr, N):
		avg = 0
		if sum(arr) % n == 0:
			avg = sum(arr) // n
			for i in range(n):
				arr[i] = abs(arr[i] - avg)
			return sum(arr) // 2
		return -1


class Solution:

	def findDifference(self, arr, N):
		c = 0
		s = 0
		for i in arr:
			s = s + i
		av = s // N
		for i in arr:
			while i < av:
				i = i + 1
				c = c + 1
		if s % n != 0:
			return -1
		else:
			return c


class Solution:

	def findDifference(self, arr, N):
		summ = sum(arr)
		if summ % N != 0:
			return -1
		else:
			a = int(summ / N)
			b = 0
			for i in range(N):
				b += abs(a - arr[i])
			return int(b / 2)


class Solution:

	def findDifference(self, arr, N):
		arr_sum = sum(arr)
		if arr_sum % n != 0:
			return -1
		val = int(arr_sum / N)
		sum_diff = 0
		for i in range(0, N):
			sum_diff += abs(arr[i] - val)
		return int(sum_diff / 2)


class Solution:

	def findDifference(self, arr, N):
		s = sum(arr)
		if s % N != 0:
			return -1
		a = s // N
		c = 0
		for i in arr:
			c += abs(i - a)
		return c // 2


class Solution:

	def findDifference(self, arr, N):
		a = sum(arr)
		if a % n != 0:
			return -1
		count = 0
		b = a // n
		for i in range(n):
			count += abs(arr[i] - b)
		return count // 2


class Solution:

	def findDifference(self, arr, N):
		if sum(arr) % N != 0:
			return -1
		val = sum(arr) // N
		ans = 0
		for i in range(N):
			ans += abs(val - arr[i])
		return ans // 2


class Solution:

	def findDifference(self, arr, N):
		av = int(sum(arr) / N)
		ct = 0
		if av * N != sum(arr):
			return -1
		for i in range(N):
			ct += abs(arr[i] - av)
		return ct // 2


class Solution:

	def findDifference(self, arr, n):
		sum = 0
		for i in range(0, n):
			sum += arr[i]
		if sum % n != 0:
			return -1
		diff_sum = 0
		eq = sum / n
		for i in range(0, n):
			diff_sum += abs(arr[i] - eq)
		return int(diff_sum / 2)
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = Solution().findDifference(a, n)
	print(ans)


class Solution:

	def findDifference(self, arr, N):
		total = sum(arr)
		if total % N != 0:
			return -1
		avg = total // N
		res = 0
		for num in arr:
			if num < avg:
				res += avg - num
		return res


class Solution:

	def findDifference(self, arr, N):
		sum = 0
		for i in range(0, N):
			sum += arr[i]
		average = int(sum / N)
		if int(sum % N) != 0:
			return -1
		total = 0
		for i in range(0, N):
			total += abs(average - arr[i])
		return int(total / 2)


class Solution:

	def findDifference(self, arr, N):
		avg = sum(arr) // N
		c = 0
		for i in arr:
			c += avg - i
		if c != 0:
			return -1
		ans = 0
		for i in arr:
			ans += avg - i if avg > i else 0
		return ans


class Solution:

	def findDifference(self, arr, N):
		sum = 0
		eq = 0
		for i in arr:
			sum += i
		if sum % N != 0:
			return -1
		else:
			eq = sum // N
		ans = 0
		for i in arr:
			ans += abs(eq - i)
		return ans // 2


class Solution:

	def findDifference(self, arr, N):
		s = sum(arr)
		if s % N:
			return -1
		avg = s // N
		l = []
		for i in arr:
			l.append(abs(i - avg))
		return sum(l) // 2


class Solution:

	def findDifference(self, arr, N):
		s1 = sum(arr)
		avg = s1 // N
		count = 0
		if s1 % N != 0:
			return -1
		pos = 0
		neg = 0
		for i in range(n):
			if arr[i] - avg > 0:
				neg = neg + arr[i] - avg
			elif arr[i] - avg < 0:
				pos = pos - arr[i] + avg
		if pos == neg:
			return pos
		else:
			return -1


class Solution:

	def findDifference(self, arr, N):
		m = N // 2
		a = [0] * N
		s = 0
		for i in range(N):
			s += arr[i]
		if s % N != 0:
			return -1
		s = s // N
		k = 0
		for i in range(N):
			k += abs(s - arr[i])
		return k // 2


class Solution:

	def findDifference(self, arr, N):
		if sum(arr) % N != 0:
			return -1
		target = int(sum(arr) / N)
		diff_sum = []
		for i in arr:
			diff_sum.append(abs(i - target))
		return int(sum(diff_sum) / 2)


class Solution:

	def findDifference(self, arr, N):
		total_sum = sum(arr)
		if total_sum % n != 0:
			return -1
		diff = 0
		eq = total_sum // n
		for i in range(n):
			diff += abs(eq - arr[i])
		return diff // 2


class Solution:

	def findDifference(self, arr, N):
		arrSum = sum(arr)
		if arrSum % N != 0:
			return -1
		arrAvg = arrSum // N
		op = 0
		for el in arr:
			op += abs(arrAvg - el)
		return op // 2