Given an array A[ ] of N integers and an integer X. In one operation, you can change the i^{th} element of the array to any integer value where 1 ≤ i ≤ N. Calculate minimum number of such operations required such that the bitwise AND of all the elements of the array is strictly greater than X.
Example 1:
Input:
N = 4, X = 2
A[] = {3, 1, 2, 7}
Output: 
2
Explanation: 
After performing two operations:
Modified array: {3, 3, 11, 7} 
Now, Bitwise AND of all the elements
is 3 & 3 & 11 & 7 = 3 
Example 2:
Input:
N = 3, X = 1
A[] = {2, 2, 2}
Output: 
0
Your Task:
You don't need to read input or print anything. Your task is to complete the function count( ) which takes N, A[ ] and X as input parameters and returns the minimum number of operations required.
Expected Time Complexity: O(N * Log(max(A[ ])))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A[i] ≤ 10^{9}
1 ≤ X ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Greedy algorithms

Starter code: #User function Template for python3
class Solution:
    def count(self, N, A, X): 
        # code here

Solutions:
class Solution:

	def count(self, N, A, X):
		prefix = 0
		ans = N
		for i in range(30, -1, -1):
			if X & 1 << i:
				prefix |= 1 << i
				continue
			cnt = 0
			prefix |= 1 << i
			for a in A:
				if a & prefix == prefix:
					cnt += 1
			ans = min(ans, N - cnt)
			prefix ^= 1 << i
		return ans


class Solution:

	def count(self, N, A, X):
		p = 0
		ans = N
		for i in range(31, -1, -1):
			if X & 1 << i:
				p |= 1 << i
			else:
				temp = p | 1 << i
				c = 0
				for j in A:
					if j & temp == temp:
						c += 1
				ans = min(ans, N - c)
		return ans


import sys

class Solution:

	def count(self, N, A, X):
		ans = sys.maxsize
		m = 0
		for i in range(31, -1, -1):
			if X >> i & 1:
				m |= 1 << i
				continue
			count = 0
			temp = m | 1 << i
			for i in range(N):
				if A[i] & temp == temp:
					count += 1
			ans = min(ans, N - count)
		return ans


class Solution:

	def count(self, N, A, X):
		res = 9223372036854775807
		curr = 0
		for i in range(31, -1, -1):
			if X >> i & 1:
				curr |= 1 << i
				continue
			temp = curr | 1 << i
			k = len(list(filter(lambda x: x & temp == temp, A)))
			res = min(res, N - k)
		return res


class Solution:

	def count(self, N, A, X):
		prefix = 0
		ans = N
		for i in range(30, -1, -1):
			if X >> i & 1 != 0:
				prefix ^= 2 ** i
				continue
			p = prefix ^ 2 ** i
			cnt = 0
			for j in A:
				if j & p == p:
					cnt += 1
			ans = min(ans, N - cnt)
		return ans


import sys

class Solution:

	def count(self, N, A, X):
		ans = float('inf')
		m = 0
		for i in range(31, -1, -1):
			if X >> i & 1:
				m |= 1 << i
				continue
			count = 0
			temp = m | 1 << i
			for i in range(N):
				if A[i] & temp == temp:
					count += 1
			ans = min(ans, N - count)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, X) = map(int, input().strip().split())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.count(N, A, X)
		print(ans)


class Solution:

	def count(self, n, arr, x):
		ans = n
		temp = 0
		for i in range(30, -1, -1):
			if x & 1 << i:
				temp += 1 << i
			else:
				c = 0
				tem = temp + (1 << i)
				for j in range(n):
					if tem & arr[j] == tem:
						c += 1
				ans = min(ans, n - c)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, X) = map(int, input().strip().split())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.count(N, A, X)
		print(ans)


class Solution:

	def count(self, N, A, X):
		ans = N
		p = 0
		for i in range(31, -1, -1):
			if X >> i & 1:
				p |= 1 << i
			else:
				temp = p | 1 << i
				c = 0
				for j in A:
					if j & temp == temp:
						c += 1
				ans = min(ans, N - c)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, X) = map(int, input().strip().split())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.count(N, A, X)
		print(ans)


class Solution:

	def count(self, N, A, X):
		ans = N
		target = 0
		for i in range(32, -1, -1):
			if X & 1 << i:
				target = target | 1 << i
			else:
				temp = target | 1 << i
				cnt = 0
				for j in range(0, N):
					if temp & A[j] == temp:
						cnt = cnt + 1
				ans = min(ans, N - cnt)
		return ans


class Solution:

	def count(self, N, A, X):
		(setbit, ans) = (0, float('inf'))
		for i in range(30, -1, -1):
			if 1 << i & X > 0:
				setbit |= 1 << i
			else:
				(temp, c) = (setbit, 0)
				temp |= 1 << i
				for i in range(N):
					if A[i] & temp != temp:
						c += 1
				ans = min(ans, c)
		return ans


class Solution:

	def count(self, n, l, x):
		flag = [False for i in range(n)]
		ans = n
		c = 1 << 32
		for i in range(31, -1, -1):
			c >>= 1
			if c & x:
				for j in range(n):
					if c & l[j] == 0:
						flag[j] = True
			else:
				t = [flag[j] for j in range(n)]
				temp = 0
				for j in range(n):
					if not t[j] and c & l[j] == 0:
						t[j] = True
					if t[j]:
						temp += 1
				ans = min(ans, temp)
		return ans


import math

class Solution:

	def count(self, n, a, x):
		if x > max(a):
			return n
		max_bl = max(a).bit_length()
		(ans, cur) = (n, 0)
		for i in range(max_bl - 1, -1, -1):
			bit = 1 << i
			if bit & x:
				cur = cur | bit
			else:
				tmp = cur | bit
				cnt = sum((v & tmp != tmp for v in a))
				ans = min(ans, cnt)
		return ans


import sys

class Solution:

	def count(self, n, a, x):
		ans = sys.maxsize
		m = 0
		for i in range(31, -1, -1):
			if x >> i & 1:
				m |= 1 << i
				continue
			count = 0
			temp = m | 1 << i
			for i in range(n):
				if a[i] & temp == temp:
					count += 1
			ans = min(ans, n - count)
		return ans


class Solution:

	def count(self, N, A, X):
		ans = N
		bitset = 0
		for i in range(31, -1, -1):
			if 1 << i & X > 0:
				bitset |= 1 << i
			else:
				x = 0
				temp = bitset | 1 << i
				for i in A:
					if i & temp == temp:
						x += 1
				x = N - x
				ans = min(ans, x)
		return ans


class Solution:

	def isBitPosSet(self, num, n):
		if num & 1 << n:
			return True
		return False

	def mostSignificantBit(self, num):
		count = 0
		while num != 0:
			num = num // 2
			count += 1
		return count - 1

	def count(self, n, a, x):
		mincount = n
		l = self.mostSignificantBit(max(a))
		m = self.mostSignificantBit(x)
		for i in range(0, l + 1):
			check = 1 << i
			if check & x:
				continue
			if check < x:
				check = x - x % check + check
			count = 0
			for j in range(n):
				if a[j] & check != check:
					count += 1
			if count < mincount:
				mincount = count
		return mincount
		return 6


import math

class Solution:

	def count(self, N, A, X):
		setBit = 0
		minValue = float('inf')
		for i in range(30, -1, -1):
			if X & 1 << i > 0:
				setBit |= 1 << i
			else:
				temp = setBit
				c = 0
				temp |= 1 << i
				for a in A:
					if temp & a != temp:
						c += 1
				minValue = min(minValue, c)
		return minValue


class Solution:

	def count(self, N, A, X):
		ans = N
		for i in range(max(A).bit_length()):
			c = 1 << i
			if c & X:
				continue
			if c < X:
				c = X - X % c + c
			count = sum((1 for b in A if b & c != c))
			ans = min(ans, count)
		return ans


class Solution:

	def check(self, X):
		ans = 0
		x = 0
		for c in X:
			if c == '1':
				x = x << 1 | 1
			else:
				x = x << 1
		for i in range(self.n):
			if x & self.arr[i] != x:
				ans += 1
		return ans

	def count(self, n, arr, x):
		self.n = n
		self.arr = arr
		X = bin(x)[2:]
		m = max(arr)
		z = len(bin(m)) - 2
		ans = n
		for l in range(len(X), z):
			ans = min(ans, self.check('1' + l * '0'))
		for i in range(len(X)):
			if X[i] == '0':
				ans = min(ans, self.check(X[:i] + '1' + '0' * (len(X) - i - 1)))
		return ans


class Solution:

	def count(self, N, A, X):
		bits_set_in_x = 0
		ans = N
		for idx in range(30, -1, -1):
			is_set_bit = 1 << idx & X
			if is_set_bit:
				bits_set_in_x |= 1 << idx
			else:
				temp = bits_set_in_x | 1 << idx
				cnt = 0
				for num in A:
					if temp & num != temp:
						cnt += 1
				ans = min(ans, cnt)
		return ans


class Solution:

	def count(self, N, A, X):
		bitSetinX = 0
		ans = N
		for i in range(32)[::-1]:
			if 1 << i & X:
				bitSetinX |= 1 << i
			else:
				temp = bitSetinX | 1 << i
				dontMdfy = 0
				for n in A:
					if n & temp == temp:
						dontMdfy += 1
				ans = min(ans, N - dontMdfy)
		return ans


class Solution:

	def count(self, N, A, X):
		res = float('inf')
		cur = 0
		for i in range(31, -1, -1):
			if X >> i & 1:
				cur |= 1 << i
				continue
			temp = cur | 1 << i
			k = len(list(filter(lambda x: x & temp == temp, A)))
			res = min(res, N - k)
		return res


class Solution:

	def count(self, N, A, x):
		p = 0
		ans = N
		for i in range(31, -1, -1):
			bit = x >> i & 1
			if bit == 1:
				p = p | 1 << i
			else:
				temp = p | 1 << i
				count = 0
				for i in A:
					if temp & i == temp:
						count += 1
			ans = min(ans, N - count)
		return ans


class Solution:

	def count(self, N, A, X):
		ans = N
		k = 0
		for i in range(30, -1, -1):
			if X & 1 << i:
				k = k | 1 << i
			else:
				temp = k | 1 << i
				c = 0
				for n in A:
					if n & temp >= temp:
						c += 1
				ans = min(ans, N - c)
		return ans


class Solution:

	def count(self, N, A, X):
		ans = N
		bitsetX = 0
		for i in range(30, -1, -1):
			if 1 << i & X:
				bitsetX |= 1 << i
			else:
				temp = bitsetX | 1 << i
				dontmodify = 0
				for number in A:
					if temp & number == temp:
						dontmodify += 1
				ans = min(ans, N - dontmodify)
		return ans


class Solution:

	def count(self, N, A, X):
		res = N
		n = max(A).bit_length()
		for i in range(n):
			check = 1 << i
			if check & X:
				continue
			if check < X:
				check = X - X % check + check
			count = sum((1 for j in A if j & check != check))
			res = min(res, count)
		return res


class Solution:

	def count(self, N, A, X) -> int:
		ans = N
		mask = 0
		for i in range(31, -1, -1):
			if X >> i & 1:
				mask ^= 1 << i
				continue
			count = 0
			temp = mask ^ 1 << i
			for j in range(N):
				if A[j] & temp != temp:
					count += 1
			ans = min(ans, count)
		return ans


class Solution:

	def count(self, N, A, X):
		result = 10000000000.0 + 1
		temp = 0
		for i in range(31, -1, -1):
			if X >> i & 1:
				temp |= 1 << i
				continue
			p = temp | 1 << i
			k = len(list(filter(lambda x: x & p == p, A)))
			result = min(result, N - k)
		return result


class Solution:

	def count(self, N, A, X):
		bitSetInX = 0
		ans = N
		for i in range(30, -1, -1):
			bit = 1 << i & X
			if bit:
				bitSetInX |= 1 << i
			else:
				temp = bitSetInX | 1 << i
				count = 0
				for element in A:
					if element & temp == temp:
						count += 1
				ans = min(ans, N - count)
		return ans


class Solution:

	def count(self, N, A, X):
		bits_set_in_X = 0
		res = N
		for i in range(30, -1, -1):
			if 1 << i & X:
				bits_set_in_X |= 1 << i
			else:
				temp = bits_set_in_X | 1 << i
				nchange = 0
				for x in A:
					if x & temp == temp:
						nchange += 1
				res = min(res, N - nchange)
		return res


class Solution:

	def count(self, N, A, X):
		B = [i for i in A if i > X]
		if not B:
			return N
		count = N - len(B)
		maxi = len(B)
		m_msb = len(str(bin(max(B)))) - 3
		for i in range(m_msb + 1):
			if X & 1 << i:
				continue
			temp = (X >> i | 1) << i
			c = 0
			for ele in B:
				if ele & temp == temp:
					c += 1
			maxi = min(maxi, len(B) - c)
		return count + maxi


class Solution:

	def count(self, N, A, X):
		mask = 0
		ans = N
		for i in range(30, -1, -1):
			if X >> i & 1:
				mask ^= 1 << i
				continue
			ct = 0
			alt_mask = mask ^ 1 << i
			for j in A:
				if j & alt_mask == alt_mask:
					ct += 1
			ans = min(ans, N - ct)
		return ans


class Solution:

	def count(self, n, a, x):
		(ans, m) = (n, 0)
		for i in range(31, -1, -1):
			t = m | 1 << i
			if x >> i & 1:
				m = t
			else:
				c = 0
				for v in a:
					if v & t == t:
						c += 1
				ans = min(ans, n - c)
		return ans


class Solution:

	def count(self, N, A, X):
		(n, arr, x) = (N, A, X)
		ans = n
		for i in range(max(arr).bit_length()):
			chk = 1 << i
			if chk & x:
				continue
			if chk < x:
				chk = x - x % chk + chk
			cnt = sum((1 for b in arr if b & chk != chk))
			ans = min(ans, cnt)
		return ans


import sys

class Solution:

	def count(self, N, A, X):
		ans = sys.maxsize
		a = 0
		for i in range(31, -1, -1):
			if X >> i & 1:
				a |= 1 << i
				continue
			c = 0
			tem = a | 1 << i
			for i in range(N):
				if A[i] & tem == tem:
					c += 1
			ans = min(ans, N - c)
		return ans


import sys

class Solution:

	def count(self, N, A, X):
		ans = sys.maxsize
		curr = 0
		for i in range(31, -1, -1):
			if X >> i & 1:
				curr |= 1 << i
				continue
			temp = curr | 1 << i
			k = len(list(filter(lambda x: x & temp == temp, A)))
			ans = min(ans, N - k)
		return ans


from collections import defaultdict

class Solution:

	def count(self, n, arr, x):
		ans = float('inf')
		mask = 0
		for i in range(31, -1, -1):
			if x & 1 << i != 0:
				mask |= 1 << i
				continue
			p = mask | 1 << i
			ct = 0
			for j in range(n):
				if arr[j] & p == p:
					ct += 1
			ans = min(ans, n - ct)
		return ans


from collections import defaultdict

class Solution:

	def count(self, n, arr, x):
		ans = 0
		cnt = [0] * 32
		x += 1
		bit = len(bin(max(max(arr), x)).replace('0b', ''))
		ans = float('inf')
		for i in range(n):
			for j in range(bit):
				if arr[i] & 1 << j != 0:
					cnt[j] += 1
		p = [0] * 32
		for j in range(bit):
			if x & 1 << j != 0:
				p[j] += 1
		for i in range(bit - 1, -1, -1):
			if p[i] > 0:
				break
			ans = min(ans, n - cnt[i])
		res = 0
		d = defaultdict(int)
		for j in range(i, -1, -1):
			if p[j] == 0:
				ans = min(ans, n - cnt[j])
				continue
			ii = 0
			while ii < len(arr):
				if d[ii] != -1 and arr[ii] & 1 << j == 0:
					res += 1
					for k in range(bit):
						if arr[ii] & 1 << k != 0:
							cnt[k] -= 1
					d[ii] = -1
				else:
					ii += 1
		ans = min(ans, res)
		return ans


import math

class Solution:

	def count(self, n, arr, x):
		p = 0
		ans = n
		for i in range(31, -1, -1):
			bit = x >> i & 1
			if bit == 1:
				p = p | 1 << i
			else:
				temp = p | 1 << i
				count = 0
				for ele in arr:
					if ele & temp == temp:
						count += 1
				ans = min(ans, n - count)
		return ans


class Solution:

	def count(self, N, A, X):
		ans = float('inf')
		m = 0
		for i in range(31, -1, -1):
			if X >> i & 1:
				m |= 1 << i
				continue
			count = 0
			temp = m | 1 << i
			for i in range(N):
				if A[i] & temp == temp:
					count += 1
			ans = min(ans, N - count)
		return ans