Given an array of integers arr[] and a query integer q. Find the number X from the array such that it can be converted from q to X such that F(q, X) is minimum.
F(A, B) = Number of bits flipped to change the number A to B.
If there are more than one values in arr[] such that F(q, X) is minimum print the smallest value of X for which F(q, X) is minimum.
Example 1:
Input:
n = 9, q = 1
arr[] = {5, 32, 1, 7, 10, 50, 19, 21, 2}
Output: 1
Explanation: F(1, 1) = 0, so this is the 
minimum X.
Example 2:
Input:
n = 6, q = 8
arr[] = {5, 32, 10, 7, 10, 50, 19, 21, 2}
Output: 10
Your Task:
You don't need to read input or print anything. Your task is to complete the function findX() which takes the array of integers arr, n and q as parameters and returns an integer denoting the answer.
Expected Time Complexity: O(n*logn)
Expected Auxiliary Space: O(1)
Constraints:
1 <= n <= 10^{5}
1 <= q <= 10^{6}
1 <= arr[i] <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3



class Solution:
    def findX(self, arr, n, q):
        # code here

Solutions:
def count(a, b):
	ans = 0
	for i in range(18):
		if a & 1 << i != b & 1 << i:
			ans += 1
	return ans

class Solution:

	def findX(self, arr, n, q):
		ans = -1
		cnt = 0
		for i in range(len(arr)):
			k = count(arr[i], q)
			if ans == -1 or cnt > k or (cnt == k and ans > arr[i]):
				ans = arr[i]
				cnt = k
		return ans


class Solution:

	def findX(self, arr, n, q):
		output = 0
		mini = float('inf')
		for num in arr:
			item = q ^ num
			count = sum((bitti == '1' for bitti in bin(item)[2:]))
			if count == mini and num < output:
				output = num
			if count < mini:
				output = num
				mini = count
		return output


class Solution:

	def findX(self, arr, n, q):
		Q = q
		res = 1 << 32
		m = 1 << 32
		for i in range(n):
			num = arr[i]
			c = 0
			while num or q:
				if num & 1 != q & 1:
					c += 1
				num >>= 1
				q >>= 1
			q = Q
			if c < m:
				m = c
				res = arr[i]
			elif c == m:
				res = min(arr[i], res)
		return res


class Solution:

	def findX(self, arr, n, q):
		min_ops = float('inf')
		min_ele = float('inf')
		for x in arr:
			res = q ^ x
			num_bits = 0
			while res > 0:
				if res & 1:
					num_bits += 1
				res = res >> 1
			if num_bits < min_ops or (num_bits == min_ops and x < min_ele):
				min_ops = num_bits
				min_ele = x
		return min_ele