Tywin Lannister is facing a war. He has N troops of soldiers. Each troop has a certain number of soldiers denoted by an array A.
Tywin thinks that a troop is lucky if it has a number of soldiers as a multiple of K. He doesn't want to lose any soldiers, so he decides to train some more.
He will win the war if he has at least half of his troops are lucky troops.
Determine the minimum number of soldiers he must train to win the war.
Example 1:
Input : arr[ ] = {5, 6, 3, 2, 1} and K = 2
Output : 1
Explanation:
Troop with 1 soldier is increased to 2.
Example 2:
Input : arr[ ] = {2, 3, 4, 9, 8, 7} and K = 4
Output :  1
Explanation:
Troop with 3 soldier is increased to 4. 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function min_soldiers() that takes an array (arr), sizeOfArray (n), an integer K, and return the minimum number of soldiers he must train to win the war. The driver code takes care of the printing.
Expected Time Complexity: O(N*LOG(N)).
Expected Auxiliary Space: O(1).
 
Constraints :
1 ≤ N, K ≤ 10^{5}
1 ≤ Ai ≤ 10^{5}

Difficulty: EASY
Tags: Sorting

Data structures
Skill types: Sorting

Data structures
Expected Time Complexity: O(N*LOG(N)).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3



def min_soldiers (arr, n, K) : 

    #Complete the function

Solutions:
def min_soldiers(arr, n, K):
	count = 0
	a = []
	i = 0
	while i < n:
		if arr[i] % K == 0:
			count += 1
		i = i + 1
	i = 0
	while i < n:
		d = K - arr[i]
		while d < 0:
			d = d + K
		a.append(d)
		i = i + 1
	a.sort()
	r = []
	m = 0
	if n % 2 == 0 and count < n // 2:
		l = n // 2 - count
		h = 0
		while h < n and len(r) < l:
			if h < len(a) and a[h] != 0:
				r.append(a[h])
			h = h + 1
		y = sum(r)
		return y
	if n % 2 == 1 and count < n // 2 + 1:
		l = n // 2 + 1 - count
		h = 0
		while h < n and len(r) < l:
			if h < len(a) and a[h] != 0:
				r.append(a[h])
			h = h + 1
		y = sum(r)
		return y
	else:
		return 0


from math import ceil

def min_soldiers(arr, n, K):
	arr.sort()
	mid = ceil(n / 2)
	count = 0
	li = []
	for i in range(n):
		if arr[i] % K != 0:
			li.append((arr[i] // K + 1) * K - arr[i])
		else:
			count += 1
	li.sort()
	if count < mid:
		diff = mid - count
		return sum(li[:diff])
	return 0


def min_soldiers(arr, n, K):
	li = []
	for i in arr:
		li.append((K - i % K) % K)
	li.sort()
	s = 0
	for i in range((n + 1) // 2):
		s = s + li[i]
	return s


def min_soldiers(arr, n, K):
	count = 0
	p = []
	for elem in arr:
		if elem % K == 0:
			count += 1
			p.append(float('inf'))
		else:
			p.append(K - elem % K)
	p.sort()
	add = 0
	index = 0
	comp = n // 2 if n % 2 == 0 else (n + 1) // 2
	while count < comp:
		if p[index] != float('inf'):
			add += p[index]
			count += 1
		else:
			break
		index += 1
	return add


import math

def min_soldiers(arr, n, K):
	mid = math.ceil(n / 2)
	count = 0
	ans = 0
	for i in range(n):
		if arr[i] % K == 0:
			count += 1
			arr[i] = 0
		else:
			arr[i] = K - arr[i] % K
	arr.sort()
	for i in range(n):
		if count >= mid:
			break
		if arr[i] == 0:
			continue
		else:
			ans += arr[i]
			count += 1
	return ans


def min_soldiers(arr, n, k):
	arr1 = []
	sum = 0
	arr.sort()
	for i in range(n):
		arr1.append((K - arr[i] % K) % K)
	arr1.sort()
	x = (n + 1) // 2
	for i in range(x):
		sum += arr1[i]
	return sum


def min_soldiers(arr, n, K):
	arr.sort()
	h = 0
	if n % 2 == 1:
		h = n // 2 + 1
	else:
		h = n // 2
	r = [[k, K - k % K] for k in arr if k % K != 0]
	r.sort(key=lambda x: x[1])
	c = 0
	for j in range(len(arr)):
		if arr[j] % K == 0:
			c += 1
	if c >= h:
		return 0
	co = 0
	count = h - c
	u = 0
	for k in r:
		co += k[1]
		u = u + 1
		if u == count:
			return co
	return co


def min_soldiers(arr, n, K):
	for i in range(n):
		temp = arr[i] % K
		if temp == 0:
			arr[i] = 0
		else:
			arr[i] = K - temp
	m = n // 2
	if n % 2 == 1:
		m += 1
	res = 0
	arr.sort()
	for i in range(m):
		res += arr[i]
	return res


import math

def min_soldiers(arr, n, K):
	count = 0
	troops = []
	for item in arr:
		if item % K == 0:
			count += 1
		else:
			troops.append(K - item % K)
	cost_of_training = 0
	troops.sort()
	number_to_train = math.ceil(n / 2) - count
	for i in range(number_to_train):
		cost_of_training += troops[i]
	return cost_of_training


def min_soldiers(arr, n, K):
	c = 0
	freq = {}
	for i in range(n):
		if arr[i] % K == 0:
			c += 1
		else:
			mod = arr[i] % K
			if mod not in freq:
				freq[mod] = 1
			else:
				freq[mod] += 1
	if n % 2 == 0:
		mid = n // 2
	else:
		mid = n // 2 + 1
	if c >= mid:
		return 0
	item = list(freq.items())
	item.sort(key=lambda x: x[0], reverse=True)
	i = 0
	mid = mid - c
	sol = 0
	while mid > 0 and i < len(item):
		if item[i][1] >= mid:
			sol += (K - item[i][0]) * mid
			mid = 0
		else:
			sol += (K - item[i][0]) * item[i][1]
			mid -= item[i][1]
		i += 1
	return sol


def min_soldiers(arr, n, K):
	res = []
	for val in arr:
		res.append((K - val % K) % K)
	res.sort()
	tot = 0
	for i in range((n + 1) // 2):
		tot += res[i]
	return tot


def min_soldiers(arr, n, K):
	l1 = []
	l2 = {}
	index = 0
	c = 0
	for i in arr:
		if i % K == 0:
			l1.append(i)
		elif i < K:
			index += 1
			l2[index] = K - i
		else:
			index += 1
			a = i // K
			l2[index] = abs(i - (a + 1) * K)
	d1 = sorted(l2.values())
	j = 0
	if n % 2 == 0:
		while len(l1) < n // 2:
			c += d1[j]
			j += 1
			l1.append(0)
	else:
		while len(l1) < n // 2 + 1:
			c += d1[j]
			j += 1
			l1.append(0)
	return c


from math import ceil

def min_soldiers(arr, n, K):
	li = []
	for i in arr:
		li.append((K - i % K) % K)
	li.sort()
	s = 0
	for i in range((n + 1) // 2):
		s += li[i]
	return s


def min_soldiers(arr, n, K):
	index = 0
	count = 0
	res = []
	sum = 0
	if n % 2 == 0:
		mid = n // 2
	else:
		mid = n // 2 + 1
	for i in range(n):
		if arr[i] % K != 0:
			a = arr[i] // K
			res.append(K * (a + 1) - arr[i])
		else:
			res.append(0)
	res.sort()
	for i in res:
		if i == 0:
			count += 1
	if count >= mid:
		return 0
	else:
		a = mid - count
		while a != 0:
			for i in res:
				if i != 0 and a != 0:
					sum += i
					a -= 1
		return sum


def min_soldiers(arr, n, K):
	temp = []
	count = 0
	for i in range(n):
		if arr[i] % K == 0:
			count += 1
		else:
			temp.append(arr[i])
	if count > n // 2:
		return 0
	temp.sort()
	if n % 2 == 1:
		j = (n + 1) // 2 - count
	else:
		j = n // 2 - count
	lst = []
	for i in range(len(temp)):
		val = temp[i]
		t = 0
		while val % K != 0:
			t += 1
			val += 1
		lst.append(t)
	lst.sort()
	return sum(lst[:j])


def min_soldiers(arr, n, K):
	c = 0
	b = []
	for i in arr:
		if i % K == 0:
			c += 1
		else:
			b.append(K - i % K)
	e = 0
	b.sort()
	d = (n + 1) // 2
	if c >= d:
		return e
	return sum(b[:d - c])


def min_soldiers(arr, n, K):
	thr = (n + 1) // 2
	ls = []
	for x in arr:
		if x % K == 0:
			ls.append(0)
		else:
			ls.append(K - x % K)
	ct = ls.count(0)
	ls.sort()
	if ct >= thr:
		return 0
	else:
		d = thr - ct
		return sum(ls[ct:ct + d])
for _ in range(0, int(input())):
	(n, K) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	ans = min_soldiers(arr, n, K)
	print(ans)


def min_soldiers(arr, n, K):
	li = []
	for i in arr:
		li.append((K - i % K) % K)
	li.sort()
	s = 0
	for i in range((n + 1) // 2):
		s = s + li[i]
	return s
for _ in range(0, int(input())):
	(n, K) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	ans = min_soldiers(arr, n, K)
	print(ans)


def min_soldiers(arr, n, K):
	for itr in range(n):
		arr[itr] = K - arr[itr] % K if arr[itr] % K != 0 else 0
	arr.sort()
	if n % 2 == 0:
		half = n // 2
	else:
		half = n // 2 + 1
	count = arr.count(0)
	if count >= half:
		return 0
	minSoldiers = 0
	for itr in range(n):
		if arr[itr] != 0:
			count += 1
			minSoldiers += arr[itr]
			if count >= half:
				return minSoldiers
	return minSoldiers
for _ in range(0, int(input())):
	(n, K) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	ans = min_soldiers(arr, n, K)
	print(ans)


def min_soldiers(arr, n, K):
	C = 0
	MIN = []
	for i in arr:
		if i % K == 0:
			C = C + 1
		else:
			MIN.append(K - i % K)
	if C >= int((n + 1) / 2):
		return 0
	else:
		MIN.sort()
		return sum(MIN[:int((n + 1) / 2) - C])


def min_soldiers(arr, n, K):
	mp = []
	for i in arr:
		mp.append((K - i) % K % K)
	mp.sort()
	x = 0
	for i in range((n + 1) // 2):
		x += mp[i]
	return x


def min_soldiers(arr, n, K):
	for i in range(n):
		arr[i] = (K - arr[i] % K) % K
	arr.sort()
	ans = 0
	for i in range((n + 1) // 2):
		ans += arr[i]
	return ans


def min_soldiers(arr, n, K):
	l = []
	count = 0
	for i in range(n):
		x = (K - arr[i] % K) % K
		l.append(x)
	l.sort()
	for i in range((n + 1) // 2):
		count += l[i]
	return count


def min_soldiers(arr, n, k):
	a = []
	for i in arr:
		a.append((k - i % k) % k)
	ans = 0
	a.sort()
	for i in range((n + 1) // 2):
		ans += a[i]
	return ans


def min_soldiers(arr, n, k):
	for i in range(n):
		arr[i] = (k - arr[i] % k) % k
	arr.sort()
	if n % 2 != 0:
		y = n // 2 + 1
	else:
		y = n // 2
	sum = 0
	for i in range(0, y, 1):
		sum += arr[i]
	return sum


import math

def min_soldiers(arr, n, k):
	for i in range(n):
		arr[i] = (k - arr[i] % k) % k
	arr.sort()
	y = math.ceil(n / 2.0)
	sum = 0
	for i in range(0, y, 1):
		sum += arr[i]
	return sum