unify-numbers

Today Omar has assignment problems from his math professor. Yes, Omar has infinite number of questions that he must solve today. The first problem went something like this.  

Given N integers in the form of A_i where 1 ≤ i ≤ N, Omar wants to make each number A_i in the N numbers equal to M. To convert a number A_i to M, it will cost |M - A_i| units. The problem asks to find out the minimum cost to convert all the N numbers to M, so you should choose the best M to get the minimum cost. 

Omar gets bored easily from these kind of questions, can you solve it for him ?

Input:

First line of the input contains an integer T denoting the number of test cases. 
First line of every test-case contains an integer N.      
Second line of every test case contains N space separated integers A_i.

Output:

For each case, print the minimum cost that Omar needs to pay to convert each A_i to M, in a separate line.   

Constraints:

1 ≤ T ≤ 10.
1 ≤ N ≤ 10 ^ 5.
1 ≤ A_i ≤ 10^{9}

SAMPLE INPUT
1
4
1 2 4 5

SAMPLE OUTPUT
6

Explanation

One of the best M's you could choose in this case is 3.   
So the answer = |1 - 3| + |2 - 3| + |4 - 3| + |5 - 3| = 6.

Source: hackerearth | Difficulty: EASY
Tags: Sorting

Implementation


Solutions:
test = int(input())
for _ in range(test):
	N = int(input())
	arr = list(map(int,input().split()))
	arr=sorted(arr)
	if N % 2 == 0:
		median = (arr[(N/2)] + arr[(N/2)-1]) / 2
	else:
		median = arr[(N/2)]
	avg = sum(arr) / N
	s1 = 0
	s2 = 0
	for i in arr:
		s1 += abs(i-median)
		s2 += abs(i-avg)
	print(min(s1,s2))


for i in range(eval(input())):
	size, bucket = eval(input()), list(map(int, input().split()))
	res = 0
	bucket.sort()
	for j in range(size):
		 res += abs(bucket[j] - bucket[size/2])
	print(res)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
for _ in range(eval(input())):
	z=int(input())
	k=list(map(int,input().split()))
	k=list(k)
	k=sorted(k)
	a=sum(k)/z
	if(z%2==0):
		m=(k[z/2]+k[(z/2)-1])/2
	else:
		m=(k[z/2])
	p=0
	q=0
	for i in k:
		p+=abs(m-i)
		q+=abs(a-i)
	print(min(p,q))



import math

t=int(input())
while t:
	t=t-1
	n = int(input())
	a = list(map(int,input().split()))
	a.sort()
	m = 0
	x=n/2
	if n%2==0:
		m = int(math.ceil((a[x-1]+a[x])/float(2)))
	else:
		m = a[x]
	cost = 0	
	for i in a:
		cost+=abs(m-i)
	print(cost)


for _ in range(eval(input())):
	z = int(input())
	a = list(map(int,input().split()))
	a=sorted(a)
	if z % 2 == 0:
		m = (a[(z/2)] + a[(z/2)-1]) / 2
	else:
		m = a[(z/2)]
	b = sum(a) / z
	p=0
	r=0
	for i in a:
		p += abs(i-m)
		r += abs(i-b)
	print(min(p,r))