Given an array arr[] of N positive elements. The task is to find the Maximum AND Value generated by any pair(arr_{i, }arr_{j}) from the array such that i != j.
Note: AND is bitwise '&' operator. 
Example 1:
Input: 
N = 4
arr[] = {4, 8, 12, 16}
Output: 8
Explanation:
Pair (8,12) has the Maximum AND Value 8.
Example 2:
Input:
N = 4
arr[] = {4, 8, 16, 2}
Output: 0
Explanation: Any two pairs of the array has 
Maximum AND Value 0.
Your Task: 
You don't need to read input or print anything. Your task is to complete the function maxAND() which takes the array elements and N (size of the array) as input parameters and returns the maximum AND value generated by any pair in the array. 
Expected Time Complexity: O(N * log M), where M is the maximum element of the array.
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{5}

Difficulty: MEDIUM
Tags: Bit manipulation

Data structures
Skill types: Bit manipulation

Data structures
Expected Time Complexity: O(N * log M), where M is the maximum element of the array.
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3

class Solution:
    #Complete this function
    # Function for finding maximum AND value.
    def maxAND(self, arr,N):
        #Your code here

Solutions:
class Solution:

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

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


class Solution:

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

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


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

class Solution:

	def maxAND(self, arr, N):
		res = 0
		for i in range(18, -1, -1):
			count = func(res | 1 << i, arr, N)
			if count >= 2:
				res = res | 1 << i
		return res


import sys

class Solution:

	def maxAND(self, arr, N):

		def countValid(arr, mask):
			count = 0
			for num in arr:
				if num & mask == mask:
					count += 1
			return count
		res = 0
		for i in range(sys.getsizeof(int()) - 1, -1, -1):
			count = countValid(arr, res | 1 << i)
			if count >= 2:
				res |= 1 << i
		return res


class Solution:

	def count(self, pattern, arr, N):
		count = 0
		for i in arr:
			if pattern & i == pattern:
				count += 1
		return count

	def maxAND(self, arr, N):
		ans = 0
		for i in range(16, -1, -1):
			if self.count(ans | 1 << i, arr, N) >= 2:
				ans |= 1 << i
		return ans


from math import log2

class Solution:

	def maxAND(self, arr, N):
		M = max(arr)
		logM = int(log2(M))
		output = 0
		while logM >= 0:
			count = 0
			check = (1 << logM) + output
			for i in range(len(arr)):
				if arr[i] & check == check:
					count += 1
			if count >= 2:
				output += 1 << logM
			logM -= 1
		return output


class Solution:

	def maxAND(self, arr, N):
		numbits = 0
		mx = 0
		for i in range(N):
			mx = max(mx, arr[i])
		while mx > 0:
			numbits += 1
			mx >>= 1
		mask = 0
		for i in range(numbits - 1, -1, -1):
			mask = mask | 1 << i
			count = 0
			for j in range(N):
				if arr[j] & mask == mask:
					count += 1
			if count <= 1:
				mask = mask & mask - 1
		return mask


class Solution:

	def maxAND(self, arr, N):
		res = 0
		for bits in range(16, -1, -1):
			count = self.checkBits(res | 1 << bits, arr, N)
			if count >= 2:
				res |= 1 << bits
		return res

	def checkBits(self, pattern, arr, N):
		count = 0
		for i in arr:
			if i & pattern == pattern:
				count += 1
		return count


class Solution:

	def maxAND(self, arr, N):

		def pat(pattern, arr, n):
			count = 0
			for i in arr:
				if i & pattern == pattern:
					count = count + 1
			return count
		res = 0
		for i in range(31, -1, -1):
			out = pat(res | 1 << i, arr, N)
			if out >= 2:
				res = res | 1 << i
		return res


class Solution:

	def maxAND(self, arr, N):
		maxAND = 0
		maxBIT = max(arr)
		maxBIT = maxBIT.bit_length()
		for bit in range(maxBIT, -1, -1):
			count = 0
			for number in arr:
				pattern = maxAND | 1 << bit
				if number & pattern == pattern:
					count += 1
				if 2 <= count:
					break
			if 2 <= count:
				maxAND |= 1 << bit
		return maxAND


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):
			pattern = res | 1 << i
			count = 0
			for j in range(len(a)):
				if a[j] & pattern == pattern:
					count += 1
			if count > 1:
				res = pattern
		return res


class Solution:

	def maxAND(self, g, n):
		ans = 0
		st = len(bin(max(g))[2:])
		for i in range(st, -1, -1):
			k = 0
			for x in g:
				if x & 1 << i != 0 and x & ans == ans:
					k += 1
			if k > 1:
				ans += 1 << i
		return ans


from math import pow

class Solution:

	def maxAND(self, arr, N):

		def check_matching_nums(pattern):
			cnt = 0
			for num in arr:
				if num & pattern == pattern:
					cnt += 1
			return cnt >= 2
		msb = len(str(bin(max(arr))))
		pattern = 0
		result = 0
		while msb >= 0:
			pattern += int(pow(2, msb))
			if check_matching_nums(pattern):
				result += int(pow(2, msb))
			else:
				pattern -= int(pow(2, msb))
			msb -= 1
		return result


class Solution:

	def checkMsbBit(self, arr, pattern):
		count = 0
		for element in arr:
			if element & pattern == pattern:
				count += 1
		return count

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


import math

class Solution:

	def maxAND(self, arr, N):
		res = 0
		for i in range(int(math.log2(max(arr))), -1, -1):
			c = self.countn(res | 1 << i, arr, N)
			if c >= 2:
				res = res | 1 << i
		return res

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


class Solution:

	def maxAND(self, arr, N):
		arr.sort()
		if N == 1:
			return 0
		i = len(arr) - 1
		x = 1
		max_ = arr[i]
		while max_ > 0:
			max_ = max_ >> 1
			x = x << 1
		x = x >> 1
		pb = x
		flag = True
		if arr[i - 1] & x == x:
			res = [x]
		else:
			res = [0]
		while pb > 0:
			cnt = 0
			for i in range(len(arr) - 1, -1, -1):
				if x & arr[i] == x:
					cnt += 1
			if cnt >= 2:
				res.append(x)
				pb = pb >> 1
				x = res[-1] | pb
			else:
				pb = pb >> 1
				x = res[-1] | pb
		return x


class Solution:

	def maxAND(self, arr, N):
		m = max(arr)
		while m & m - 1 > 0:
			m = m & m - 1
		val = 0
		j = m
		while m > 0:
			count = 0
			for i in arr:
				if j & i == j:
					count += 1
			if count > 1:
				val = val | m
			m = m >> 1
			j = val | m
		return val


def check(arr, pt):
	cnt = 0
	for i in arr:
		if i & pt == pt:
			cnt += 1
		if cnt >= 2:
			return True
	return False

class Solution:

	def maxAND(self, arr, N):
		res = 0
		for i in range(16, -1, -1):
			pt = res | 1 << i
			if check(arr, pt):
				res = pt
		return res


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

def maxAN(arr, n):
	res = 0
	m = max(arr)
	for bit in range(len(bin(m)) - 2, -1, -1):
		count = checkBit(res | 1 << bit, arr, n)
		if count >= 2:
			res = res | 1 << bit
	return res

class Solution:

	def maxAND(self, arr, N):
		return maxAN(arr, N)


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

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

class Solution:

	def maxAND(self, arr, N):
		return maxAN(arr, N)


class Solution:

	def maxAND(self, arr, N):
		val = 0
		for i in range(16, -1, -1):
			count = 0
			for j in arr:
				if j & val >= val and j & 1 << i:
					count += 1
			if count >= 2:
				val += 1 << i
		return val


class Solution:

	def maxAND(self, arr, N):
		res = 0
		for powOf2 in range(31, -1, -1):
			pattern = res | 1 << powOf2
			count = 0
			for i in arr:
				if pattern & i == pattern:
					count += 1
			if count >= 2:
				res |= 1 << powOf2
		return res


class Solution:

	def maxAND(self, arr, N):
		c = 1
		res = 0
		q = 0
		for i in range(16, -1, -1):
			c = 1 << i
			d = 0
			for j in arr:
				if (res | c) & j == res | c:
					d = d + 1
			if d >= 2:
				res = res | c
		return res


class Solution:

	def maxAND(self, arr, N):
		res = 0
		for setbit in range(31, -1, -1):
			x = res | 1 << setbit
			c = 0
			for i in arr:
				if x & i == x:
					c += 1
			if c >= 2:
				res = res | 1 << setbit
		return res


class Solution:

	def maxAND(self, arr, N):
		if N == 1:
			return 0
		ans = ''
		newArr = arr.copy()
		for i in range(18):
			flag = False
			cnt = 0
			arr = newArr.copy()
			for ii in range(len(arr)):
				if arr[ii] & 1 << 18 - i - 1 == 1 << 18 - i - 1:
					cnt += 1
			if cnt > 1:
				newArr = []
				flag = True
			if flag == False:
				ans += '0'
			else:
				ans += '1'
			if flag:
				for ii in range(len(arr)):
					if arr[ii] & 1 << 18 - i - 1 == 1 << 18 - i - 1:
						newArr.append(arr[ii])
						continue
		return int(ans, 2)


class Solution:

	def maxAND(self, arr, N):

		def check(pattern, arr, n):
			count = 0
			for i in range(n):
				if arr[i] & pattern == pattern:
					count += 1
			return count
		res = 0
		m = max(arr)
		key = 0
		for i in range(31, -1, -1):
			if m & 1 << i:
				key = i
				break
		for i in range(key + 1, -1, -1):
			count = check(res | 1 << i, arr, N)
			if count >= 2:
				res = res | 1 << i
		return res


import math

class Solution:

	def maxAND(self, arr, N):

		def countNumber(curr):
			count = 0
			for num in arr:
				if curr & num == curr:
					count += 1
			return count
		ans = 0
		for i in range(31, -1, -1):
			if countNumber(ans | 1 << i) >= 2:
				ans |= 1 << i
		return ans


class Solution:

	def maxAND(self, arr, N):
		if N <= 1:
			return 0
		m = arr[0]
		for x in arr[1:]:
			m = max(m, x)
		numBits = 0
		while m > 0:
			numBits += 1
			m //= 2
		mask = 0
		while numBits > 0:
			mask |= 1 << numBits - 1
			cnt = 0
			for x in arr:
				if mask & x == mask:
					cnt += 1
			if cnt < 2:
				mask &= ~(1 << numBits - 1)
			numBits -= 1
		res = ~0
		for x in arr:
			if mask & x == mask:
				res &= x
		return res


from math import log2

class Solution:

	def maxAND(self, arr, N):
		try:
			l = int(log2(max(arr)))
		except:
			l = 1
		bitset = 0
		for i in range(l, -1, -1):
			(temp, count) = (bitset | 1 << i, 0)
			for num in arr:
				if num & temp == temp:
					count += 1
			if count >= 2:
				bitset |= 1 << i
		return bitset


class Solution:

	def checkbits(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(16, -1, -1):
			count = self.checkbits(res | 1 << bit, arr, N)
			if count >= 2:
				res = res | 1 << bit
		return res


class Solution:

	def maxAND(self, arr, N):
		m = 1
		res = 0
		i = 31
		while i >= 0:
			res = res | m << i
			count = 0
			for ele in arr:
				if res & ele == res:
					count += 1
			if count < 2:
				res = res & res - 1
			i -= 1
		return res


import math

class Solution:

	def maxAND(self, arr, N):

		def checkBit(pat, arr, n):
			cnt = 0
			for i in range(0, n):
				if pat & arr[i] == pat:
					cnt += 1
			return cnt
		res = 0
		for bit in range(int(math.log2(max(arr)) + 1), -1, -1):
			count = checkBit(res | 1 << bit, arr, N)
			if count >= 2:
				res = res | 1 << bit
		return res


class Solution:

	def isBitTwice(self, arr, pos, val):
		count = 0
		for i in arr:
			if val & i == val:
				count = count + 1
		return count

	def maxAND(self, arr, N):
		maxsum = 0
		for i in reversed(range(0, 31)):
			count = self.isBitTwice(arr, N, maxsum | 1 << i)
			if count >= 2:
				maxsum = maxsum | 1 << i
		return maxsum


class Solution:

	def maxAND(self, arr, N):

		def check(res, arr):
			count = 0
			for i in range(len(arr)):
				if arr[i] & res == res:
					count += 1
			return count
		ans = 0
		for i in range(16, -1, -1):
			res = ans | 1 << i
			x = check(res, arr)
			if x > 1:
				ans = res
		return ans


class Solution:
	import math

	def maxAND(self, arr, n):
		max = 0
		for j in range(n):
			if arr[j] > max:
				max = arr[j]
		bits = math.floor(math.log(max, 2))
		x = 2 ** bits
		bit = bits + 1
		base = 2 ** bit - 1

		def bit_reset(x, bit, base):
			res = x & (base ^ 1 << bit - 1)
			return res

		def bit_set(x, bit):
			res = x | 1 << bit - 1
			return res
		ans = 0
		while bit > 0:
			count = 0
			for i in range(n):
				if arr[i] & x == x:
					count += 1
			if count >= 2:
				if x > ans:
					ans = x
			else:
				x = bit_reset(x, bit, base)
			if bit > 1:
				x = bit_set(x, bit - 1)
			bit -= 1
		return ans


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):
			c = self.check(res | 1 << i, arr, N)
			if c >= 2:
				res = res | 1 << i
		return res


class Solution:

	def maxAND(self, arr, N):
		import math
		max2 = int(math.log2(10 ** 5))
		res = 0
		for i in range(max2, -1, -1):
			count = 0
			pattern = res | 1 << i
			for j in range(len(arr)):
				if arr[j] & pattern == pattern:
					count += 1
			if count > 1:
				res |= 1 << i
		return res


class Solution:

	def maxAND(self, arr, N):
		max1 = 0
		for i in range(31, -1, -1):
			count = 0
			z = max1 | 1 << i
			for j in arr:
				if j & z == z:
					count += 1
			if count >= 2:
				max1 |= 1 << i
		return max1


class Solution:

	def maxAND(self, arr, N):
		res = 0
		for i in range(31, -1, -1):
			count = 0
			patt = res | 1 << i
			for t in arr:
				if t & patt == patt:
					count += 1
			if count >= 2:
				res = res | 1 << i
		return res


class Solution:

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

	def countKSetBit(self, arr, k):
		c = 0
		for i in arr:
			if i & k == k:
				c += 1
		return c


class Solution:

	def maxAND(self, arr, N):
		for i in range(31, -1, -1):
			l = []
			for j in arr:
				if j & 1 << i != 0:
					l.append(j)
			if len(l) > 1:
				arr = l
		if len(arr) > 1:
			ma = arr[0]
			for i in arr:
				ma = ma & i
			return ma
		else:
			return 0


class Solution:

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

	def maxAND(self, arr, N):
		res = 0
		for i in range(16, -1, -1):
			cnt = self.match(res | 1 << i, arr)
			if cnt >= 2:
				res |= 1 << i
		return res


class Solution:

	def checkbit(self, pattern, arr):
		count = 0
		for j in range(0, len(arr)):
			if pattern & arr[j] == pattern:
				count += 1
		return count

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


class Solution:

	def checkIfTwoExists(self, arr, pattern):
		count = 0
		for num in arr:
			if num & pattern == pattern:
				count += 1
		return count >= 2

	def maxAND(self, arr, N):
		ans = 0
		for place in range(16, -1, -1):
			pattern = ans | 1 << place
			if self.checkIfTwoExists(arr, pattern):
				ans = pattern
		return ans


class Solution:

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

	def maxAND(self, arr, N):
		obj1 = Solution()
		res = 0
		for i in range(18, -1, -1):
			x = res | 1 << i
			count = obj1.check(x, arr, N)
			if count >= 2:
				res = x
		return res


class Solution:

	def maxAND(self, A, N):
		mask = 0
		for i in range(16, -1, -1):
			t = mask | 1 << i
			c = 0
			for j in range(N):
				if t & A[j] == t:
					c += 1
			if c >= 2:
				mask = t
		return mask


class Solution:

	def maxAND(self, arr, N):
		ans = 0
		for i in range(21, -1, -1):
			k = 1 << i
			k = k | ans
			cnt = 0
			for i in range(N):
				if arr[i] & k == k:
					cnt += 1
			if cnt >= 2:
				ans = k
		return ans


class Solution:

	def maxAND(self, arr, N):
		temp = 0
		for i in range(31, -1, -1):
			temp1 = temp | 1 << i
			count = 0
			for j in arr:
				if j & temp1 == temp1:
					count += 1
			if count >= 2:
				temp = temp1
		return temp


class Solution:

	def maxAND(self, arr, N):
		lis = []
		for i in range(31, -1, -1):
			bitn = 1 << i
			l = []
			for j in arr:
				if j & bitn:
					l.append(j)
			if len(l) >= 2:
				lis.append(i)
				arr = l
		res = 0
		for i in lis:
			res += 2 ** i
		return res


class Solution:

	def maxAND(self, arr, N):
		l1 = []
		for i in range(31, -1, -1):
			k = 1 << i
			l = [m for m in arr if m & k != 0]
			if len(l) >= 2:
				l1.append(i)
				arr = l
		v = 0
		for k in l1:
			v += 2 ** k
		return v


class Solution:

	def countAND(self, arr, N, X):
		count = 0
		for i in range(N):
			if arr[i] & X == X:
				count += 1
		return count

	def maxAND(self, arr, N):
		res = 0
		j = 16
		while j + 1 > 0:
			x = 1 << j
			x += res
			countAv = self.countAND(arr, N, x)
			if countAv >= 2:
				res = x
			j -= 1
		return res


class Solution:

	def maxAND(self, arr, N):
		ans = 0
		for i in range(16, -1, -1):
			power = 1 << i
			count = 0
			for num in arr:
				if num & ans == ans and num & power:
					count += 1
			if count >= 2:
				ans += power
		return ans


class Solution:

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

	def maxAND(self, arr, N):
		res = 0
		arr.sort()
		k = int(math.log(arr[N - 1], 2))
		for bit in range(k, -1, -1):
			c = self.checkBit(res | 1 << bit, arr, N)
			if c >= 2:
				res |= 1 << bit
		return res


import math

class Solution:

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

	def maxAND(self, arr, N):
		arr.sort()
		k = int(math.log(arr[N - 1], 2))
		res = 0
		for i in range(k, -1, -1):
			s = Solution()
			cnt = s.count(res | 1 << i, arr)
			if cnt >= 2:
				res |= 1 << i
		return res


class Solution:

	def maxAND(self, arr, N):
		maxand = 0
		maxbit = max(arr)
		maxbit = maxbit.bit_length()
		for bit in range(maxbit, -1, -1):
			count = 0
			for n in arr:
				pattern = maxand | 1 << bit
				if n & pattern == pattern:
					count += 1
				if 2 <= count:
					break
			if 2 <= count:
				maxand |= 1 << bit
		return maxand


class Solution:

	def checkbit(self, p, arr, n):
		c = 0
		for j in arr:
			if p & j == p:
				c += 1
		return c

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


class Solution:

	def check(self, p, arr, N):
		c = 0
		for i in range(N):
			if arr[i] & p == p:
				c += 1
				if c == 2:
					return True
		return False

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