You are given an array of N integers A[0], A[1], …, A[N-1], and an integer k. Your task is to make all the elements of the given array equal in a minimum number of ‘moves’.  All the elements of the array are non-negative. In each ‘move,’ you may add or subtract k from any element of the array. Give the answer modulo 10^{9}+7.
Example 1:
Input: N = 4, k = 2
A = {7, 5, 21, 17}
Output: 13
Explaination: We can add k = 2 to A[1] 
once and subtract k = 2 from A[2] seven 
times and from A[3] five times.The 
resulting array would be- 7 7 7 7. 
Number of moves = 1 + 7 + 5 = 13.
Example 2:
Input: N = 4, k = 3
A = {7, 5, 21, 17}
Output: -1
Explaination: No matter how many moves 
are made, all the elements of the array 
cannot be made equal.
Your Task:
You do not need to read input or print anything. Your task is to complete the function equalizeArray() which takes N, k, and A as input parameters and returns the minimum number of moves to make all the elements of the array equal. Return -1 if it is not possible.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ k, A[i] ≤ 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Mathematics

Starter code: #User function Template for python3



class Solution:

    def equalizeArray(self, N, k, A):

        # code here

Solutions:
class Solution:

	def equalizeArray(self, n, k, a):
		if n == 1:
			return 0
		m = 0
		a.sort()
		if n % 2 == 1:
			mid = n // 2
		else:
			mid = n // 2 - 1
		for i in range(n):
			if abs(a[mid] - a[i]) % k != 0:
				return -1
			else:
				s = abs(a[mid] - a[i])
				m += s // k
		return m % (10 ** 9 + 7)


class Solution:

	def equalizeArray(self, N, k, A):
		A.sort()
		count = 0
		l = (N - 1) // 2
		for i in range(N):
			if A[i] != A[l]:
				count += abs(A[l] - A[i]) // k
				if A[i] > A[l]:
					A[i] -= k * (abs(A[l] - A[i]) // k)
				else:
					A[i] += k * (abs(A[l] - A[i]) // k)
		s = set(A)
		if len(s) != 1:
			return -1
		return int(count % (1000000000.0 + 7))


class Solution:

	def equalizeArray(self, N, k, A):
		if N == 1:
			return 0
		moves = 0
		A.sort()
		if N % 2 == 1:
			mid = N // 2
		else:
			mid = N // 2 - 1
		for i in range(N):
			if abs(A[mid] - A[i]) % k != 0:
				return -1
			else:
				s = abs(A[mid] - A[i])
				moves += s // k
		return moves % (10 ** 9 + 7)


class Solution:

	def equalizeArray(self, N, k, A):
		A.sort()
		mid = A[N // 2]
		move = 0
		for i in range(N):
			if abs(A[i] - mid) % k == 0:
				move += abs(A[i] - mid) // k
			else:
				return -1
		return int(move % (1000000000.0 + 7))


class Solution:

	def upper_bound(self, a, l, r, k):
		pos = r + 1
		while l <= r:
			mid = (l + r) // 2
			if a[mid] >= k:
				pos = mid
				l = mid - 1
			else:
				r = mid + 1
		return pos

	def equalizeArray(self, N, k, A):
		A.sort()
		MOD = 10 ** 9 + 7
		ans = 0
		if N % 2 == 1:
			mid = N // 2
			for i in range(0, N):
				if abs(A[i] - A[mid]) % k != 0:
					return -1
				diff = abs(A[i] - A[mid])
				diff = diff // k
				ans = (ans + diff) % MOD
		else:
			mid = N // 2 - 1
			for i in range(0, N):
				if abs(A[i] - A[mid]) % k != 0:
					return -1
				diff = abs(A[i] - A[mid])
				diff = diff // k
				ans = (ans + diff) % MOD
		return ans


class Solution:

	def equalizeArray(self, N, k, A):
		steps = 0
		A.sort()
		mid = 0
		if N % 2 == 1:
			mid = N // 2
		else:
			mid = N // 2 - 1
		for i in range(N):
			if abs(A[i] - A[mid]) % k != 0:
				return -1
		for i in range(N):
			diff = abs(A[i] - A[mid])
			steps += diff // k % 1000000007
		return steps % 1000000007


class Solution:

	def equalizeArray(self, N, k, A):
		nums = A
		nums.sort()
		(low, high) = (0, len(nums) - 1)

		def check(mid):
			sum1 = 0
			for i in range(len(nums)):
				if (nums[i] - mid) % k != 0:
					return -1
				else:
					sum1 = sum1 + abs(nums[i] - mid) // k
			return sum1
		while low < high:
			mid = (low + high) // 2
			if check(nums[mid]) <= check(nums[mid - 1]) and check(nums[mid]) <= check(nums[mid + 1]):
				if check(nums[mid]) == -1:
					return -1
				else:
					return check(nums[mid]) % 1000000007
			elif check(nums[mid + 1]) > check(nums[mid]):
				high = mid - 1
			else:
				low = mid + 1
		return min(check(min(nums)), check(max(nums))) % 1000000007


class Solution:

	def equalizeArray(self, N, k, A):
		mod = 10 ** 9 + 7
		steps = 0
		A.sort()
		if N % 2 == 1:
			mid = N // 2
		else:
			mid = N // 2 - 1
		for i in range(N):
			if abs(A[i] - A[mid]) % k != 0:
				return -1
		for i in range(N):
			steps += abs(A[i] - A[mid]) / k % mod
		return int(steps % mod)