Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef Tobby is trying to run a code given to him by Bhuvan for an experiment they want to include in the manuscript to be submitted to a conference. The deadline to submit the manuscript is within a couple of hours and Chef Tobby needs to finish the experiments before then.

The code given by Bhuvan is the following which runs given an array of N integers and another integer K :

void recurse ( array a, int n )
{
	// n = size of array
	define array b currently empty
	consider all 2^{n} subsets of a[]
	{
		x = bitwise OR of elements in the subsets
		add x into "b" if it is not present yet
	}
	if (sizeof( b ) == 1 < k)
	{
		printf(“Won”);
		return;
	}
	recurse ( b, sizeof( b ) );
}

Chef Tobby tried to run an experiment with only one integer in the array with value 2 and K = 3. To his horror, he found out that the algorithm is resulting in an infinite loop. He is livid with the possibility that the algorithm can lead to infinite loops for certain cases. On closer inspection he determines that it might be possible to insert additional elements in the initial array to subvert the problem. Since time is very less, Chef Tobby would like to insert the minimum number of elements.

Chef Tobby has to finish writing the paper, so he asks his graduate student Leamas to fix it. Leamas has no idea how to fix the problem so he asks you for help.

------ Input section ------ 

The first line contains T, the number of test cases.

Each test case consists of 2 lines. The first line contains 2 integers N and K, denoting the number of elements in the array and parameter mentioned in problem statement.

Next line contains N space separated integers, denoting the elements of the array.

------ Output section ------ 

Output the minimum number of elements that need to be inserted so that inifinite loop can be avoided.

------ Input constraints ------ 

1 ≤ T ≤ 10
1 ≤ Sum of N over all test cases ≤ 10^{5}
1 ≤ K ≤ 20
0 ≤ A[i] ≤ 2^{K}-1, where A[i] denotes the i^{th} element of the array.

----- Sample Input 1 ------ 
1
2 2
3 1
----- Sample Output 1 ------ 
1
----- explanation 1 ------ 
You can win the game by inserting the element 2 into the array.

----- Sample Input 2 ------ 
1
7 3
3 7 5 4 6 2 1
----- Sample Output 2 ------ 
0
----- explanation 2 ------ 
The initial array will result will terminate in the first step of algorithm only. Thus there is no need to insert any new element.

Source: codechef | Difficulty: HARD
Tags: Bit manipulation

Mathematics

Greedy algorithms


Solutions:
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	c = 0
	for i in range(k):
		if 2 ** i not in x:
			c += 1
	print(c)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	nums = [int(i) for i in input().split()]
	ans = 0
	mask = 1 << k - 1
	while mask:
		if mask not in nums:
			ans += 1
		mask = mask >> 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(k):
		if 2 ** i not in arr:
			count += 1
	print(count)


T = int(input())
for t in range(T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	for i in range(k):
		if 2 ** i not in a:
			count += 1
	print(count)


T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	a = set(list(map(int, input().split())))
	count = 0
	for j in range(k):
		if 1 << j not in a:
			count += 1
	print(count)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = set(list(map(int, input().split())))
	c = 0
	for j in range(k):
		if 1 << j not in a:
			c += 1
	print(c)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(set(map(int, input().split())))
	c = 0
	for i in range(k):
		if 1 << i not in l:
			c = c + 1
	print(c)


ck = lambda : map(int, input().split())
for _ in range(int(input())):
	(n, k) = ck()
	a = list(set(ck()))
	c = 0
	for i in range(k):
		if 1 << i not in a:
			c += 1
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	for i in range(k):
		s = pow(2, i)
		if s not in a:
			c += 1
	print(c)


def ip():
	return int(input())

def ipp():
	return map(int, input().split())

def sar():
	return list(ipp())

def pars(a):
	print(' '.join(list(map(str, a))))
	print('\r')

def parl(a):
	print('\r'.join(list(map(str, a))))
	print('\r')
T = 1
T = int(input().strip())
for _ in range(T):
	(n, k) = ipp()
	a = []
	a = sar()
	b = []
	for i in a:
		if i > 0 and i & i - 1 == 0:
			b.append(i)
	d = set(b)
	print(k - len(d))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = []
	for i in range(n):
		if l[i] > 0:
			if l[i] & l[i] - 1 == 0:
				s.append(l[i])
	s = set(s)
	print(k - len(s))


def solve(x, k):
	x = set(x)
	for i in range(k):
		if 1 << i in x:
			k -= 1
	return k
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	(n, k) = map(int, f.readline().split())
	x = list(map(int, f.readline().split()))
	print(solve(x, k))


t = input()
t = int(t)
ans = []
for i in range(t):
	y = 0
	a = list(map(int, input().split(' ')))
	n = a[0]
	k = a[1]
	a = list(map(int, input().split(' ')))
	for i in range(k):
		if 2 ** i not in a:
			y = y + 1
	ans.append(y)
for i in ans:
	print(i)


t = int(input())
for _ in range(t):
	a = input().split()
	n = int(a[0])
	k = int(a[1])
	a = input().split()
	a = [int(x) for x in a]
	c = 0
	i = 1
	p = pow(2, k) - 1
	while i <= p:
		if i not in a:
			c += 1
		i = i * 2
	print(c)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	count = 0
	arr = [int(p) for p in input().split()]
	must_have_nos = {}
	for j in range(k):
		must_have_nos[2 ** j] = False
	for l in arr:
		if l in must_have_nos:
			must_have_nos[l] = True
	for m in must_have_nos:
		if not must_have_nos[m]:
			count += 1
	print(count)


import math
for qq in range(int(input())):
	(n, k) = map(int, input().strip().split(' '))
	a = set(map(int, input().strip().split(' ')))
	ans = 0
	for i in range(0, k):
		te = int(math.pow(2, i))
		if not te in a:
			ans = ans + 1
	print(ans)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	for j in range(0, k):
		if 2 ** j not in a:
			count += 1
	print(count)
	t -= 1


def is_power(a):
	if not a & a - 1:
		return True
	return False
tc = int(input())
for i in range(0, tc):
	(n, k) = map(lambda x: int(x), input().split())
	array = set(map(lambda x: int(x), input().split()))
	ans = sum([1 if j != 0 and is_power(j) else 0 for j in array])
	ans = 0 if ans >= k else k - ans
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = set(arr)
	c = 0
	arr = list(set(arr))
	for j in range(k + 1):
		x = 2 ** j
		if x in arr:
			c += 1
	print(k - c)


for i in range(int(input())):
	(d, k) = map(int, input().split())
	n = map(int, input().split())
	n = list(n)
	add = 0
	j = 0
	while j < k:
		tk = 2 ** j
		ll = 0
		pp = 0
		while ll < d:
			if n[ll] == tk:
				pp = 1
				break
			ll += 1
		if pp == 0:
			add += 1
		j += 1
	print(add)


t = int(input())
ans = []
for i in range(t):
	(n, k) = list(map(int, input().split()))
	numbers = list(map(int, input().split()))
	present = [False for j in range(k)]
	for number in numbers:
		binary = bin(number)
		idx = 0
		if number != 0 and number & number - 1 == 0:
			present[len(binary) - 2 - 1] = True
	count = 0
	for cond in present:
		if cond == False:
			count += 1
	if count == 0:
		ans.append(0)
	else:
		ans.append(count)
for x in ans:
	print(x)


import math
for _ in range(int(input())):
	str = list(map(int, input().split()))
	n = str[0]
	k = str[1]
	s = set(list(map(int, input().split())))
	ans = 0
	for i in range(0, k):
		te = math.pow(2, i)
		if not te in s:
			ans = ans + 1
	print(ans)


for _ in range(int(input())):
	S = set()
	(N, K) = map(int, input().split())
	Present = [0] * K
	Check = [2 ** i for i in range(K)]
	ARR = list(map(int, input().split()))
	for i in ARR:
		for j in range(K):
			if Check[j] == i:
				Present[j] = 1
	count_zeros = 0
	for i in Present:
		if i == 0:
			count_zeros += 1
	print(count_zeros)


powers = [2 ** i for i in range(20)]
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ints = set(list(map(int, input().split())))
	count = 0
	for i in ints:
		if i in powers:
			count += 1
	print(k - count)


T = int(input())
while T > 0:
	T -= 1
	(N, K) = [int(x) for x in input().split()]
	arr = set([int(x) for x in input().split()])
	cnt = 0
	for i in range(K):
		if 1 << i not in arr:
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	[n, k] = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	a = list(set(a))
	di = {}
	for i in a:
		di[i] = 1
	j = 1
	t = 1 << k
	ans = 0
	while j < t:
		try:
			l = di[j]
		except:
			ans += 1
		j <<= 1
	print(ans)


for t in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	x = 0
	for i in range(K):
		if 1 << i not in A:
			x += 1
	print(x)


def list_input():
	return list(map(int, input().split()))

def map_input():
	return map(int, input().split())

def map_string():
	return input().split()
for _ in range(int(input())):
	(n, k) = map_input()
	a = list_input()
	s = set(a)
	b = []
	for i in range(k):
		if 1 << i not in s:
			b.append(1 << i)
	print(len(b))