Given an array arr[] of N positive elements. The task is to find the Maximum AND Value generated by any pair of elements from the array.
Note: AND is bitwise '&' operator. 
Example 1:
Input : Arr[] = {4, 8, 12, 16}
Output : 8
Explanation:
Pair (8,12) has the Maximum AND Value
i.e. 8.
Example 2:
Input : Arr[] = {4, 8, 16, 2} 
Output : 0
Your Task:
The input is already taken care of by the driver code. You only need to complete the function maxAND() that takes an array (arr), size of Array (n) as parameter and return the maximum AND value of pair. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 5*10^{5}
1 <= arr[i] <= 5*10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3
class Solution:

	def maxAND (self,arr,  n) :
		# Complete the function

Solutions:
class Solution:

	def maxAND(self, arr, n):
		ans = 0
		for i in range(18, -1, -1):
			temp = []
			for a in arr:
				if a & 1 << i:
					temp.append(a)
			if len(temp) == 2:
				return temp[0] & temp[1]
			elif len(temp) > 2:
				arr = temp
				ans += 1 << i
		return ans


import math

class Solution:

	def maxAND(self, a, n):
		res = 0
		x = max(a)
		h = math.floor(math.log2(x)) + 1
		for i in range(h - 1, -1, -1):
			count = 0
			pattern = res | 1 << i
			for j in range(len(a)):
				if a[j] & pattern == pattern:
					count += 1
			if count > 1:
				res |= 1 << i
		return res


class Solution:

	def checkBit(self, pattern, arr, n):
		count = 0
		for i in range(0, n):
			if pattern & arr[i] == pattern:
				count = count + 1
		return count

	def maxAND(self, arr, n):
		res = 0
		for bit in range(31, -1, -1):
			count = self.checkBit(res | 1 << bit, arr, n)
			if count >= 2:
				res = res | 1 << bit
		return res


class Solution:

	def maxAND(self, arr, n):
		arr.sort()
		ans = 0
		for i in range(1, len(arr)):
			ans = max(ans, arr[i] & arr[i - 1])
		return ans


class Solution:

	def maxAND(self, arr, n):
		res = 0
		if n == 1:
			return 0
		arr.sort()
		for i in range(n - 1):
			res = max(res, arr[i] & arr[i + 1])
		return res


class Solution:

	def maxAND(self, arr, n):
		res = 0
		for i in range(31, -1, -1):
			check = res | 1 << i
			cnt = 0
			for j in range(n):
				if arr[j] & check == check:
					cnt += 1
			if cnt >= 2:
				res = res | 1 << i
		return res


class Solution:

	def checkPattern(self, bitPattern, arr, n):
		count = 0
		for i in range(n):
			if arr[i] & bitPattern == bitPattern:
				count += 1
		return count

	def maxAND(self, arr, n):
		maxANDValue = 0
		itemCount = 0
		for bit in range(18, -1, -1):
			bitPattern = maxANDValue | 1 << bit
			itemCount = self.checkPattern(bitPattern, arr, n)
			if itemCount >= 2:
				maxANDValue = maxANDValue | 1 << bit
		return maxANDValue


def check(pfm, mask, arr):
	c = 0
	for i in arr:
		if mask & i == mask:
			c += 1
	return c

class Solution:

	def maxAND(self, arr, n):
		max = 0
		mask = 0
		pfm = 0
		for i in range(31, -1, -1):
			mask = max | 1 << i
			pfm |= 1 << i
			if check(pfm, mask, arr) >= 2:
				max = mask
		return max


class Solution:

	def maxAND(self, arr, n):
		arr.sort()
		max_val = 0
		for i in range(n - 1):
			max_val = max(max_val, arr[i] & arr[i + 1])
		return max_val


class Solution:

	def maxAND(self, arr, n):

		def checkCount(x):
			count = 0
			for i in arr:
				if i & x == x:
					count += 1
			return count
		res = 0
		for i in reversed(range(19)):
			x = res | 1 << i
			count = checkCount(x)
			if count >= 2:
				res = x
		return res


class Solution:

	def maxAND(self, arr, n):
		arr.sort()
		m = 0
		for i in range(n - 1, 0, -1):
			if i > 0:
				if m < arr[i] & arr[i - 1]:
					m = arr[i] & arr[i - 1]
		return m
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	print(ob.maxAND(arr, n))


class Solution:

	def maxAND(self, arr, n):
		if n == 1:
			return 0
		arr.sort()
		mx = -1
		i = n - 1
		while i >= 0:
			if i > 0:
				mx = max(mx, arr[i] & arr[i - 1])
			i -= 1
		return mx


class Solution:

	def check(self, pattern, arr, n):
		c = 0
		for i in arr:
			if i & pattern == pattern:
				c += 1
		return c

	def maxAND(self, arr, n):
		res = 0
		for i in range(31, -1, -1):
			count = self.check(res | 1 << i, arr, n)
			if count >= 2:
				res |= 1 << i
		return res


class Solution:

	def maxAND(self, arr, n):
		r = 0
		for i in range(31, -1, -1):
			c = 0
			t = r | 1 << i
			for e in arr:
				if e & t == t:
					c += 1
			if c > 1:
				r = t
		return r


class Solution:

	def maxAND(self, arr, n):

		def check(val):
			count = 0
			for i in range(n):
				if arr[i] & val == val:
					count += 1
			if count >= 2:
				return True
			return False
		binary = bin(max(arr))[2:]
		bits = len(binary)
		res = 0
		temp = 1
		for i in range(bits - 1, -1, -1):
			temp = 1 << i
			if check(res | temp):
				res = res | temp
		return res


class Solution:

	def maxAND(self, arr, n):
		arr.sort()
		arr = arr[::-1]
		m = 0
		for i in range(n - 1):
			if m < arr[i] & arr[i + 1]:
				m = arr[i] & arr[i + 1]
		return m


class Solution:

	def maxAND(self, arr, n):
		ans = 0
		for i in range(31, -1, -1):
			curr = ans | 1 << i
			count = 0
			for j in range(0, n):
				if curr & arr[j] == curr:
					count += 1
			if count >= 2:
				ans = curr
		return ans


class Solution:

	def maxAND(self, elements, n):
		pattern_count = lambda elements, pattern: sum((1 for element in elements if element & pattern == pattern))
		pattern = 0
		for bit_position in range(31, -1, -1):
			if pattern_count(elements, pattern | 1 << bit_position) > 1:
				pattern |= 1 << bit_position
		return pattern