A drawer contains socks of n different colours. The number of socks available of i^{th} colour is given by a[i] where a is an array of n elements. Tony wants to take k pairs of socks out of the drawer. However, he cannot see the colour of the sock that he is picking. You have to tell what is the minimum number of socks Tony has to pick in one attempt from the drawer such that he can be absolutely sure, without seeing their colours, that he will have at least k matching pairs.
Example 1:
Input:
N = 4, K = 6
a[] = {3, 4, 5, 3}
Output: 15
Explanation: 
All 15 socks have to be picked in order
to obtain 6 pairs.
Example 2:
Input: N = 2, K = 3
a[] = {4, 6}
Output: 7
Explanation: The Worst case scenario after 6
picks can be {3,3} or {1,5} of each
coloured socks. Hence 7th pick will ensure
3rd pair. 
Your Task:  
You don't need to read input or print anything. Complete the function find_min() which takes the array a[], size of array N, and value K as input parameters and returns the minimum number of socks Tony has to pick. If it is not possible to pick then return -1. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5} 
1 ≤ a[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3


class Solution:
    def find_min(self, a, n, k):
        #Code Here



Solutions:
class Solution:

	def find_min(self, a, n, k):
		total = sum((sock // 2 for sock in a))
		if total < k:
			return -1
		ans = 2 * k
		odd = 0
		even = 0
		for i in range(n):
			if a[i] % 2:
				odd += 1
			elif a[i] != 0 and a[i] % 2 == 0:
				even += 1
		return ans + odd + min(even - 1, total - k)


class Solution:

	def find_min(self, a, n, k):
		maxpair = 0
		even = 0
		for i in range(n):
			maxpair += a[i] // 2
			if a[i] % 2 == 0:
				even += 1
		if k > maxpair:
			return -1
		if even <= maxpair - k:
			ans = k * 2 + (n - 1)
		else:
			ans = k * 2 + n - (even - (maxpair - k))
		return ans


class Solution:

	def find_min(self, a, n, k):
		total = 0
		chosen = 0
		for i in range(n):
			total += a[i] // 2
			if a[i] % 2 != 0:
				chosen += (a[i] - 1) // 2
			else:
				chosen += (a[i] - 2) // 2
		if total < k:
			return -1
		elif chosen >= k:
			return 2 * (k - 1) + (n + 1)
		else:
			return 2 * chosen + n + (k - chosen)


class Solution:

	def find_min(self, a, n, k):
		p = 0
		sum_ = 0
		for i in range(n):
			p += a[i] // 2
			if a[i] % 2 == 0:
				sum_ += (a[i] - 2) // 2
			else:
				sum_ += (a[i] - 1) // 2
		if p < k:
			return -1
		elif sum_ >= k:
			return 2 * (k - 1) + n + 1
		else:
			return 2 * sum_ + n + (k - sum_)


class Solution:

	def find_min(self, a, n, k):
		SP = 0
		res = n
		for i in range(len(a)):
			if i < n and SP < k:
				a[i] -= 1
				while a[i] >= 2:
					SP += 1
					if SP == k:
						res += 1
						break
					a[i] -= 2
					res += 2
		for j in range(n):
			if j < n and SP < k:
				if a[j] > 0:
					SP += 1
					res += 1
		return res if SP == k else -1


class Solution:

	def find_min(self, a, n, k):
		l = []
		r = n
		x = 0
		socks = 0
		for i in a:
			l.append(i - 1)
		for i in range(n):
			if socks + l[i] // 2 >= k:
				y = k - socks
				socks += y
				r += 2 * y - 1
			else:
				y = l[i] // 2
				socks += y
				r += 2 * y
			l[i] = l[i] % 2
			if socks == k:
				break
		if socks == k:
			return r
		else:
			for i in l:
				if i == 1:
					r += 1
					socks += 1
				if socks == k:
					break
		if socks == k:
			return r
		else:
			return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		k = int(input())
		obj = Solution()
		print(obj.find_min(a, n, k))


class Solution:

	def find_min(self, a, n, k):
		count = n
		pairs = 0
		pot_pairs = 0
		for (i, el) in enumerate(a):
			if a[i] & 1:
				count += a[i] - 1
				pairs += a[i] // 2
			else:
				count += a[i] - 2
				pairs += (a[i] - 1) // 2
				pot_pairs += 1
			if pairs >= k:
				return count - (pairs - k) * 2 - 1
		return count + (k - pairs) if pot_pairs >= k - pairs else -1


class Solution:

	def find_min(self, a, n, k):
		p = 0
		q = 0
		for i in a:
			p += i // 2
			q += (i - 1) // 2
		if p < k:
			return -1
		if k > q:
			return n + k + q
		return n + (2 * k - 1)


class Solution:

	def find_min(self, a, n, k):
		totalNumOfSocks = 0
		numOfPairs = 0
		for i in range(0, n):
			totalNumOfSocks += 1
			a[i] -= 1
		if numOfPairs < k:
			for i in range(0, n):
				totalNumOfPairsOfCurrentColor = a[i] // 2
				remainingSocksOfCurrentColor = a[i] % 2
				a[i] = remainingSocksOfCurrentColor
				if numOfPairs + totalNumOfPairsOfCurrentColor >= k:
					totalNumOfSocks = totalNumOfSocks + 2 * (k - numOfPairs)
					numOfPairs = k
				else:
					totalNumOfSocks = totalNumOfSocks + 2 * totalNumOfPairsOfCurrentColor
					numOfPairs += totalNumOfPairsOfCurrentColor
				if numOfPairs == k:
					totalNumOfSocks -= 1
					break
			for i in range(0, n):
				if numOfPairs == k:
					break
				if a[i] == 1:
					totalNumOfSocks += 1
					numOfPairs += 1
		if numOfPairs == k:
			return totalNumOfSocks
		else:
			return -1


class Solution:

	def find_min(self, a, n, k):
		p = 0
		ans = -1
		opt = 0
		for i in a:
			p += i // 2
			if i % 2 == 1:
				opt += (i - 1) // 2
			else:
				opt += (i - 2) // 2
		if p < k:
			return ans
		if k <= opt:
			ans = 2 * (k - 1) + n + 1
		else:
			ans = 2 * opt + (k - opt) + n
		return ans


class Solution:

	def find_min(self, a, n, k):
		sum = 0
		even = 0
		for i in a:
			sum += i
			even += 1 - i & 1
		last = sum - even + 1
		ans = n + k * 2 - 1
		diff = ans - last
		if diff > 0:
			ans -= diff // 2
		return ans if ans <= sum else -1


class Solution:

	def find_min(self, a, n, k):
		s = 0
		complete_pairs = 0
		for i in range(0, n):
			complete_pairs += a[i] // 2
			if a[i] % 2 == 0:
				s += (a[i] - 2) // 2
			else:
				s += (a[i] - 1) // 2
		if k > complete_pairs:
			return -1
		if k <= s:
			return 2 * (k - 1) + n + 1
		return 2 * s + n + (k - s)


class Solution:

	def find_min(self, a, n, k):
		if k > sum((x // 2 for x in a)):
			return -1
		m = sum(((x - 1) // 2 for x in a))
		return n + k * 2 - 1 if m >= k else n + m + k


class Solution:

	def find_min(self, a, n, k):
		sum1 = sum(a)
		check = 0
		totalpair = 0
		for i in range(n):
			totalpair = totalpair + a[i] // 2
			if a[i] % 2 == 0:
				check = check + (a[i] - 2) // 2
			else:
				check = check + (a[i] - 1) // 2
		if totalpair < k:
			return -1
		if check >= k:
			return 2 * (k - 1) + (n + 1)
		else:
			return 2 * check + n + (k - check)


class Solution:

	def find_min(self, a, n, k):
		total = sum(a)
		even = 0
		for val in a:
			even += 1 - val % 2
		ans = n + (k - 1) * 2 + 1
		last = total - even + 1
		diff = ans - last
		if diff > 0:
			ans -= diff // 2
		if ans <= total:
			return ans
		return -1


class Solution:

	def find_min(self, a, n, k):
		result = n
		pair = 0
		for i in range(n):
			a[i] = a[i] - 1
			while a[i] >= 2:
				pair += 1
				if pair == k:
					result += 1
					return result
				result += 2
				a[i] = a[i] - 2
		for i in range(n):
			if a[i] > 0:
				pair += 1
				result += 1
			if pair == k:
				return result
		if pair == k:
			return result
		else:
			return -1


class Solution:

	def find_min(self, a, n, k):
		cnt = 0
		cnt2 = 0
		for i in range(n):
			cnt += (a[i] + 1) // 2 - 1
			cnt2 += a[i] % 2 == 0
		if cnt2 + cnt < k:
			return -1
		return n + 2 * k - max(1, k - cnt)


class Solution:

	def find_min(self, a, n, k):
		(pairs, ans) = (0, 0)
		for (idx, num) in enumerate(a):
			pairs += num // 2
			if num % 2 == 1:
				ans += (num - 1) // 2
			else:
				ans += (num - 2) // 2
		if pairs < k:
			return -1
		if ans >= k:
			return 2 * k + n - 1
		return 2 * ans + n + (k - ans)


class Solution:

	def find_min(self, a, n, k):
		res = n
		sp = 0
		i = 0
		while sp < k and i < n:
			a[i] -= 1
			while a[i] >= 2:
				sp += 1
				if sp == k:
					res += 1
					break
				res += 2
				a[i] -= 2
			i += 1
		i = 0
		while sp < k and i < n:
			if a[i] > 0:
				sp += 1
				res += 1
			i += 1
		return res if sp == k else -1


class Solution:

	def find_min(self, a, n, k):
		l = 0
		min = 0
		for i in range(n):
			l += a[i] // 2
			if a[i] % 2 == 0:
				min += (a[i] - 2) // 2
			else:
				min += (a[i] - 1) // 2
		if l < k:
			return -1
		elif min >= k:
			return 2 * (k - 1) + n + 1
		return 2 * min + n + k - min


class Solution:

	def find_min(self, a, n, k):
		arr = a
		N = n
		K = k
		(pair, su) = (0, 0)
		for i in range(N):
			pair += a[i] // 2
			if a[i] % 2 == 0:
				su += (a[i] - 2) // 2
			else:
				su += (a[i] - 1) // 2
		if pair < K:
			return -1
		elif su >= K:
			return 2 * (K - 1) + (N + 1)
		else:
			return 2 * su + N + (K - su)


class Solution:

	def find_min(self, a, n, k):
		sp = 0
		for x in a:
			sp += x // 2
		if sp < k:
			return -1
		opt = 0
		for x in a:
			if x % 2 == 0:
				opt += (x - 2) // 2
			else:
				opt += (x - 1) // 2
		if opt >= k:
			return 2 * (k - 1) + n + 1
		else:
			return 2 * opt + n + k - opt


class Solution:

	def find_min(self, a, n, k):
		total_pairs = 0
		for i in a:
			total_pairs += i // 2
		if total_pairs < k:
			return -1
		else:
			sumx = 0
			for i in a:
				if i & 1:
					sumx += i // 2
				else:
					sumx += i // 2 - 1
			if sumx >= k:
				return 2 * (k - 1) + n + 1
			else:
				return sumx * 2 + n + k - sumx
		return 0


class Solution:

	def find_min(self, a, n, k):
		pair = 0
		k -= 1
		ans = 0
		rem = []
		for i in range(len(a)):
			if a[i] % 2 == 0:
				b = a[i] - 1
			else:
				b = a[i]
			z = min((k - pair) * 2 + 1, b)
			ans += z
			pair += z // 2
			rem.append(a[i] - z)
		k += 1
		p = k - pair
		for i in range(len(rem)):
			item = rem[i]
			if item != 0:
				ans += 1
				p -= 1
			if p == 0:
				return ans
		if p == 0:
			return ans
		return -1


class Solution:

	def find_min(self, arr, n, k):
		(maxPairs, poss) = (0, 0)
		for a in arr:
			maxPairs += a // 2
			if a % 2 == 0:
				poss += (a - 2) // 2
			else:
				poss += a // 2
		if k > maxPairs:
			return -1
		elif k <= poss:
			return 2 * (k - 1) + n + 1
		else:
			return 2 * poss + (k - poss) + n


class Solution:

	def find_min(self, a, n, k):
		c1 = 0
		c2 = 0
		for i in range(n):
			c1 += (a[i] + 1) // 2 - 1
			c2 += a[i] % 2 == 0
		if c1 + c2 < k:
			return -1
		else:
			return 2 * k + n - max(1, k - c1)


class Solution:

	def find_min(self, arr, n, k):
		even = 0
		total = 0
		for i in arr:
			even += 1 - i % 2
			total += i
		last = total - even + 1
		ans = n + 2 * k - 1
		diff = ans - last
		if diff > 0:
			ans -= diff // 2
		return ans if ans <= total else -1


class Solution:

	def find_min(self, a, n, k):
		if n == 1 and a[n - 1] == 3:
			return 2
		if n == 1 and a[n - 1] == 1:
			return -1
		else:
			cnt = 0
			for i in a:
				if i % 2 == 0:
					cnt = cnt + 1
			even = cnt
			total = sum(a)
			ans = n + k * 2 - 1
			last = total - even + 1
			diff = ans - last
			if diff > 0:
				ans -= diff // 2
			if ans <= total:
				return ans
			else:
				return -1


class Solution:

	def find_min(self, arr, n, k):
		pairs = 0
		ans = n
		i = 0
		while i < n and pairs < k:
			arr[i] -= 1
			while a[i] >= 2:
				pairs += 1
				if pairs == k:
					ans += 1
					break
				ans += 2
				a[i] -= 2
			i += 1
		j = 0
		while j < n and pairs < k:
			if a[j] > 0:
				pairs += 1
				ans += 1
			j += 1
		if pairs == k:
			return ans
		else:
			return -1


class Solution:

	def find_min(self, a, n, k):
		(pair, tot) = (0, 0)
		for i in range(n):
			pair += a[i] // 2
			if a[i] % 2 == 0:
				tot += (a[i] - 2) // 2
			else:
				tot += (a[i] - 1) // 2
		if pair < k:
			return -1
		elif tot >= k:
			return 2 * (k - 1) + n + 1
		else:
			return 2 * tot + n + (k - tot)


class Solution:

	def find_min(self, a, n, k):
		s = 0
		for i in a:
			s = s + i // 2
		if k > s:
			return -1
		m = 0
		for i in a:
			if i % 2 == 0:
				m = m + i // 2 - 1
			else:
				m = m + i // 2
		if k <= m:
			return 2 * (k - 1) + n + 1
		else:
			return 2 * m + abs(k - m) + n


class Solution:

	def find_min(self, a, n, k):
		count1 = 0
		count2 = 0
		for i in range(n):
			count1 += (a[i] + 1) // 2 - 1
			count2 += a[i] % 2 == 0
		if count1 + count2 < k:
			return -1
		else:
			return 2 * k + n - max(1, k - count1)


class Solution:

	def find_min(self, a, n, k):
		total = 0
		even = 0
		ans = 2 * k + n - 1
		for i in range(n):
			total += a[i]
			even += 1 - a[i] % 2
		last = total - even + 1
		dif = ans - last
		if dif > 0:
			ans -= dif // 2
		return ans if ans <= total else -1


class Solution:

	def find_min(self, a, n, k):
		(x, y) = (0, 0)
		for i in range(n):
			(x, y) = (x + (a[i] + 1) // 2 - 1, y + (a[i] % 2 == 0))
		return n + 2 * k - max(1, k - x) if x + y >= k else -1


class Solution:

	def find_min(self, a, n, k):
		count = n
		sockpair = 0
		for i in range(n):
			if sockpair < k:
				a[i] -= 1
				while a[i] >= 2:
					sockpair += 1
					if sockpair == k:
						count += 1
						break
					count += 2
					a[i] -= 2
		for i in range(n):
			if sockpair < k:
				if a[i] > 0:
					sockpair += 1
					count += 1
		return count if sockpair == k else -1


class Solution:

	def find_min(self, arr, N, k):
		pairs = 0
		opt = 0
		for i in range(N):
			pairs += arr[i] // 2
		for i in arr:
			if i % 2 == 1:
				opt += (i - 1) // 2
			if i % 2 == 0:
				opt += (i - 2) // 2
		if k > pairs:
			return -1
		if k <= opt:
			return 2 * (k - 1) + N + 1
		elif k > opt:
			return 2 * opt + (k - opt) + N


class Solution:

	def find_min(self, a, n, k):
		min_possible = sum(((e - 1) // 2 for e in a))
		even = sum((e % 2 == 0 for e in a))
		possible = sum((e // 2 for e in a))
		res = min((k - 1) * 2 + n + 1, sum(a) - even + max(0, min(even, k - min_possible)))
		return res if k <= possible else -1