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):
		(res, bitset) = (N, 0)
		for i in range(32, -1, -1):
			if X & 1 << i > 0:
				bitset |= 1 << i
			else:
				count = 0
				temp = bitset | 1 << i
				for num in A:
					if num & temp != temp:
						count += 1
				res = min(res, count)
		return res


class Solution:

	def count(self, N, A, X):
		(res, bitset) = (float('inf'), 0)
		for i in range(30, -1, -1):
			if X & 1 << i > 0:
				bitset |= 1 << i
			else:
				count = 0
				temp = bitset | 1 << i
				for num in A:
					if num & temp != temp:
						count += 1
				res = min(res, count)
		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 ^= 1 << i
				continue
			ct = 0
			p = prefix ^ 1 << i
			for j in range(N):
				if A[j] & p == p:
					ct += 1
			ans = min(ans, N - ct)
		return ans


class Solution:

	def count(self, N, A, X):
		res = N
		bitsetinX = 0
		for i in range(31, -1, -1):
			if X & 1 << i:
				bitsetinX |= 1 << i
			else:
				mayberes = bitsetinX | 1 << i
				noneedtochange = 0
				for i in A:
					if i & mayberes == mayberes:
						noneedtochange += 1
				res = min(res, N - noneedtochange)
		return res
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 = 10 ** 9 + 9
		cur_xor = 0
		for i in range(31, -1, -1):
			if X & 1 << i:
				cur_xor = cur_xor | 1 << i
			else:
				temp = cur_xor | 1 << i
				cnt = 0
				for i in range(0, N):
					if temp & A[i] == temp:
						cnt = cnt + 1
				ans = min(ans, N - cnt)
		return ans


class Solution:

	def count(self, N, A, X):
		m = A[0]
		for i in range(1, N):
			m &= A[i]
		ans = N
		for i in range(32):
			if 1 << i | m > X:
				c = 0
				for x in A:
					if x & 1 << i == 0:
						c += 1
				ans = min(ans, c)
		s = set()
		for i in range(31, -1, -1):
			if 1 << i & X != 0:
				for (j, x) in enumerate(A):
					if 1 << i & x == 0:
						s.add(j)
			else:
				t = set()
				for (j, x) in enumerate(A):
					if 1 << i & x == 0:
						t.add(j)
				ans = min(ans, len(s | t))
		return ans


class Solution:

	def count(self, n, l, x):

		def fun(t):
			c = 0
			for i in l:
				if t & i != t:
					c += 1
			return c
		maxv = max(l)
		ans = n
		for i in range(maxv + 1):
			a = 1 << i
			t = x + a - x % a
			if t > maxv:
				break
			ans = min(ans, fun(t))
		return ans