Read problems statements in Mandarin Chinese . 

Given an array of n non-negative integers: A_{1}, A_{2}, …, A_{N}. Your mission is finding a pair of integers A_{u}, A_{v} (1 ≤  u < v ≤ N) such that (A_{u} and A_{v}) is as large as possible.
And is a bit-wise operation which is corresponding to & in C++ and Java.

------ Input ------ 

The first line of the input contains a single integer N. The ith line in the next N lines contains the A_{i}.

------ Output ------ 

Contains a single integer which is the largest value of A_{u} and A_{v} where 1 ≤  u < v ≤ N.

------ Constraints ------ 

50 points:
$2 ≤ N ≤ 5000$
$0 ≤ A_{i} ≤ 10^{9}$
50 points:
$2 ≤ N ≤ 3 × 10^{5}$
$0 ≤ A_{i} ≤ 10^{9}$

----- Sample Input 1 ------ 
4
2
4
8
10
----- Sample Output 1 ------ 
8
----- explanation 1 ------ 
2 and 4 = 0
2 and 8 = 0
2 and 10 = 2
4 and 8 = 0
4 and 10 = 0
8 and 10 = 8

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics

Greedy algorithms
Skill types: Bit manipulation

Greedy algorithms

Starter code:

Solutions:
A = []
for _ in range(int(input())):
	A.append(int(input()))
s = -1
A.sort()
for i in range(len(A) - 1, -1, -1):
	if A[i] & A[i - 1] > s:
		s = A[i] & A[i - 1]
print(s)


def pairAndSum(arr, n):
	ans = []
	for i in range(1, n):
		ans.append(arr[i - 1] & arr[i])
	return ans
n = int(input())
arr = []
for i in range(n):
	arr.append(int(input()))
arr.sort()
print(max(pairAndSum(arr, n)))


ans = 0
a = []
n = int(input())
for _ in range(n):
	a.append(int(input()))
a.sort()
for i in range(n - 1, 1, -1):
	ans = max(ans, a[i] & a[i - 1])
print(ans)


def solve():
	arr = []
	n = int(input())
	for _ in range(n):
		arr.append(int(input()))
	ans = 0
	for j in range(31, -1, -1):
		temp = []
		for ele in arr:
			if ele & 1 << j:
				temp.append(ele)
		if len(temp) >= 2:
			ans += 1 << j
			arr = temp
	print(ans)
solve()


def andope(n, m):
	for i in range(len(n) - 1):
		m = max(m, n[i] & n[i + 1])
	print(m)
n = [int(input()) for i in range(int(input()))]
m = 0
n = sorted(n)
andope(n, m)


s = []
l = []
for _ in range(int(input())):
	l.append(int(input()))
v = 0
for i in l:
	if i > v:
		for j in s:
			if i & j > v:
				v = i & j
		s.append(i)
print(v)


N = int(input())
A = []
maxx = 0
for i in range(N):
	A.append(int(input()))
A.sort(reverse=True)
for i in range(len(A)):
	if maxx > A[i]:
		break
	for j in range(len(A)):
		if j > i:
			if A[i] & A[j] > maxx:
				maxx = A[i] & A[j]
			if maxx > A[j]:
				continue
print(maxx)


t = eval(input())
lst = []
for i in range(t):
	n = eval(input())
	lst.append(n)
lst.sort()
m = 0
for i in range(len(lst) - 1):
	m = max(m, lst[i] & lst[i + 1])
print(m)


from math import ceil, sqrt, log, gcd
from collections import deque, defaultdict as dd
from os import path
import sys
t = int(input())
a = []
new = []
v = 0
for f in range(t):
	a.append(int(input()))
for i in a:
	if i > v:
		for j in new:
			if i & j > v:
				v = i & j
		new.append(i)
print(v)


from sys import stdin, stdout
input = stdin.readline
n = int(input().strip())
arr = [int(input().strip()) for _ in range(n)]
binary = [bin(num).split('b')[1].rjust(30, '0') for num in arr]
ans = [0 for _ in range(30)]
index = list(range(n))
for j in range(30):
	count = 0
	temp = []
	for i in index:
		bit = binary[i][j]
		if bit == '1':
			temp.append(i)
			count += 1
	if count > 1:
		ans[j] = 1
		index = temp
ans = ans[::-1]
res = 0
mul = 1
for i in range(30):
	res += mul * ans[i]
	mul *= 2
print(res)


from math import log

def count_same_log_res(l, log_res):
	count = 0
	for x in l:
		if x == 0:
			continue
		if int(log(x, 2)) == log_res:
			count += 1
	return count
N = int(input(''))
l = []
for i in range(N):
	l.append(int(input('')))
and_res = 0
while len(l) > 0:
	max_int = max(l)
	max_log_res = int(log(max_int, 2))
	if count_same_log_res(l, max_log_res) > 1:
		and_res += 2 ** max_log_res
		l = [x - 2 ** max_log_res for x in l if x > 2 ** max_log_res]
	else:
		for i in range(len(l)):
			if l[i] == max_int:
				l[i] -= 2 ** max_log_res
	l = [x for x in l if x > 0]
print(and_res)


def check(p, a, n):
	c = 0
	for i in range(n):
		if p & a[i] == p:
			c += 1
	return c

def AND(a, n):
	r = 0
	for i in range(31, -1, -1):
		count = check(r | 1 << i, a, n)
		if count >= 2:
			r = r | 1 << i
	return r
n = int(input())
a = []
for i in range(n):
	a.append(int(input()))
print(AND(a, n))


n = int(input())
arr = []
for i in range(0, n):
	arr.append(int(input()))
s = 0
arr.sort(reverse=True)
for i in range(0, n - 1):
	s = max(s, arr[i] & arr[i + 1])
print(s)


import sys
n = int(input())
s = [int(j) for j in sys.stdin.read().split()]
large_values = []
value = 0
for num in s:
	if num > value:
		for m in large_values:
			if m & num > value:
				value = m & num
		large_values.append(num)
print(value)


import sys
from collections import Counter
import numpy as np
import math
test = False

def next_level(B, digit):
	C = []
	for num in B:
		if num[digit] == '1':
			C.append(num)
	if len(C) >= 2:
		return C
	else:
		return B
N = int(input().strip())
A = []
for i in range(N):
	temp = int(input().strip())
	temp = '{0:b}'.format(temp)
	temp = '0' * (30 - len(temp)) + temp
	if test:
		print(temp)
	A.append(temp)
answer = 0
B = A.copy()
for digit in range(30):
	B = next_level(B, digit)
	if len(B) == 2:
		answer = int('0b' + B[0], 2) & int('0b' + B[1], 2)
if answer == 0:
	answer = int('0b' + B[0], 2) & int('0b' + B[1], 2)
print(answer)
if test:
	print(' ')


N = int(input())
l = []
for i in range(N):
	l.append(int(input()))
l.sort(reverse=True)
ans = 0
for i in range(min(len(l), 5)):
	for j in range(len(l)):
		if i == j:
			continue
		ans = max(l[i] & l[j], ans)
print(ans)


num = []
for _ in range(int(input())):
	num.append(int(input()))
num.sort(reverse=True)
ans = 0
for i in range(min(len(num), 5)):
	for j in range(len(num)):
		if i == j:
			continue
		ans = max(num[i] & num[j], ans)
print(ans)


n = int(input())
dp = []
while n > 0:
	dp.append(int(input()))
	n -= 1
mask = 1 << 30
maxx = 0
for bitt in range(30, -1, -1):
	dpp = []
	for i in dp:
		if i & mask != 0:
			dpp.append(i)
	if len(dpp) >= 2:
		dp = dpp[:]
		maxx += mask
	mask >>= 1
print(maxx)


try:
	n = int(input())
	arr = []
	for _ in range(n):
		arr.append(int(input()))
	maxx = 0
	arr.sort()
	for i in range(len(arr) - 1):
		maxx = max(maxx, arr[i] & arr[i + 1])
	print(maxx)
except:
	pass


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

def maxAND(arr, n):
	res = 0
	for bit in range(31, -1, -1):
		count = checkBit(res | 1 << bit, arr, n)
		if count >= 2:
			res |= 1 << bit
	return res
arr = []
n = int(input())
for i in range(n):
	kk = int(input())
	arr.append(kk)
print(maxAND(arr, n))


n = int(input())
l = []
for _ in range(n):
	l.append(int(input()))
l.sort(reverse=True)
ans = 0
for i in range(n - 1):
	if ans > l[i]:
		break
	m = l[i] & l[i + 1]
	if m > ans:
		ans = m
print(ans)


n = int(input())
a = []
for i in range(n):
	x = int(input())
	a.append(x)
c = 0
for i in range(31, -1, -1):
	temp = []
	for j in range(len(a)):
		if a[j] & 1 << i:
			temp.append(a[j])
	if len(temp) >= 2:
		c += 1 << i
		a = temp
print(c)


arr = []
for _ in range(int(input())):
	arr.append(int(input()))
arr.sort()
Max = -1
for i in range(len(arr) - 1):
	if arr[i] & arr[i + 1] > Max:
		Max = arr[i] & arr[i + 1]
print(Max)


li = []
for _ in range(int(input())):
	li.append(int(input()))
li.sort()
m = -1
for i in range(len(li) - 1, 1, -1):
	if li[i] & li[i - 1] > m:
		m = li[i] & li[i - 1]
print(m)


import sys, math
n = int(input())
arr = []
for _ in range(n):
	i = int(input())
	arr.append(i)
ispresent = [True for i in range(n)]
ans = 0
for j in range(32, -1, -1):
	count = 0
	for i in range(len(arr)):
		if ispresent[i] and arr[i] & 1 << j:
			count += 1
	if count >= 2:
		ans = ans | 1 << j
		for i in range(len(arr)):
			if ispresent[i]:
				ispresent[i] = arr[i] & 1 << j > 0
print(ans)


import heapq

def andOperation():
	n = int(input())
	h = []
	for i in range(n):
		heapq.heappush(h, int(input()))
	curr = heapq.heappop(h)
	ans = 0
	while h:
		t2 = heapq.heappop(h)
		ans = max(ans, t2 & curr)
		curr = t2
	print(ans)
andOperation()


try:
	N = int(input())
	a = []
	for T in range(N):
		x = int(input())
		a.append(x)
	C = 0
	for i in range(31, -1, -1):
		temp = []
		for j in range(len(a)):
			if a[j] & 1 << i:
				temp.append(a[j])
		if len(temp) >= 2:
			C += 1 << i
			a = temp
	print(C)
except:
	pass


import math

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

def find_maxand(arr):
	ans = 0
	for i in range(31, -1, -1):
		if returnmbset(arr, ans | 1 << i) >= 2:
			ans |= 1 << i
	return ans
n = int(input())
arr = list()
while n:
	arr.append(int(input()))
	n -= 1
print(find_maxand(arr))


N = int(input())
nums = []
for n in range(N):
	nums.append(int(input()))
availID = [n for n in range(N)]
mask = 1 << 30
maxAnd = 0
for bit in range(30, -1, -1):
	onesID = []
	for i in availID:
		if nums[i] & mask != 0:
			onesID.append(i)
	if len(onesID) >= 2:
		maxAnd += mask
		availID = onesID[:]
	mask >>= 1
print(maxAnd)


for W in range(1):
	N = int(input())
	L = []
	for x in range(N):
		tmp = int(input())
		L.append(tmp)
	for p in range(35, -1, -1):
		val = 2 ** p
		newL = []
		c = 0
		for x in range(len(L)):
			if L[x] & val:
				newL.append(L[x])
				c += 1
		if c > 1:
			L = newL
	print(L[0] & L[1])


t = int(input())
l = []
for i in range(t):
	n = int(input())
	l.append(n)
m = 0
l.sort()
for i in range(len(l) - 1):
	m = max(m, l[i] & l[i + 1])
print(m)


a = []
for i in range(int(input())):
	n = int(input())
	a.append(n)

def fn(a):
	bit = len(bin(max(a))) - 1
	ans = 0
	for i in range(bit, -1, -1):
		s1 = []
		s2 = []
		if len(a) == 2:
			return a[0] & a[1]
		for j in a:
			if j & 1 << i:
				s1.append(j)
			else:
				s2.append(j)
		if len(s1) >= 2:
			a = s1
			ans += 1 << i
	return ans
print(fn(a))


n = int(input())
l = [0] * n
for _ in range(n):
	l[_] = int(input())
x = 0
p = []
for i in range(30):
	for z in l:
		if z & 2 ** (29 - i):
			p.append(z)
	if len(p) > 1:
		l = p
		x += 2 ** (29 - i)
	p = []
print(x)


import math as m
n = int(input())
a = []
for i in range(n):
	a.append(int(input()))
v = max(a)
l = int(m.log(v, 2))
a.sort(reverse=True)
curr = a
flag = False
for i in range(l, -1, -1):
	new = []
	temp = []
	for j in range(len(curr)):
		t = curr[j] // 2 ** i
		if t == 1:
			new.append(a[j])
			temp.append(curr[j] % 2 ** i)
	if len(new) < 2:
		curr = [x % 2 ** i for x in curr]
		continue
	elif len(new) == 2:
		print(new[0] & new[1])
		flag = True
		break
	else:
		a = new
		curr = temp
if not flag:
	v = a[0] & a[1]
	for i in range(2, len(a)):
		v &= a[i]
	print(v)


n = int(input())
arr = []
m = -1
for i in range(n):
	arr.append(int(input()))
arr.sort(reverse=True)
for i in range(n - 1):
	if m > arr[i]:
		break
	temp = arr[i] & arr[i + 1]
	if temp > m:
		m = temp
print(m)


maxim = 0
n = int(input())
l = []
maxim = 0
for i in range(n):
	l.append(int(input()))
l.sort()
for i in range(n - 1):
	maxim = max(maxim, l[i] & l[i + 1])
print(maxim)


n = int(input())
lst = []
for i in range(n):
	lst.append(int(input()))
lst.sort()
m = 0
for i in range(len(lst) - 1):
	m = max(m, lst[i] & lst[i + 1])
print(m)


N = int(input())
l = []
for _ in range(N):
	l.append(int(input()))
l.sort()
a = 0
for i in range(N - 1):
	b = l[i] & l[i + 1]
	if b > a:
		a = b
print(a)


listx = sorted(list((int(input()) for x in range(int(input())))))
maxx = 0
for i in range(len(listx) - 1):
	maxx = max(maxx, listx[i] & listx[i + 1])
print(maxx)


n = int(input())
L = []
for i in range(n):
	a = int(input())
	L.append(a)
i = 35
L.sort()
while i >= 0 and len(L) > 2:
	M = []
	for j in range(len(L)):
		if L[j] & 1 << i:
			M.append(L[j])
	if len(M) >= 2:
		L = M
	i -= 1
print(L[0] & L[1])


l = [int(input()) for i in range(int(input()))]
m = 0
l = sorted(l)
for i in range(len(l) - 1):
	m = max(m, l[i] & l[i + 1])
print(m)


num = []
for _ in range(int(input())):
	num.append(int(input()))
num.sort(reverse=True)
ans = 0
for i in range(len(num) - 1):
	ans = max(num[i] & num[i + 1], ans)
print(ans)


l = []
for _ in range(int(input())):
	l.append(int(input()))
l.sort()
m = 0
for i in range(len(l) - 1):
	m = max(m, l[i] & l[i + 1])
print(m)


from math import *
from collections import *
from functools import *

def rvi():
	return [*map(int, input().split())]
(n,) = rvi()
t = []
for _ in range(n):
	(x,) = rvi()
	t += [x]
t.sort(reverse=1)
print(max((a & b for (a, b) in zip(t, t[1:]))))


n = int(input())
l = []
for i in range(n):
	l.append(int(input()))
l.sort(reverse=True)
x = 0
for i in range(1, n):
	x = max(l[i] & l[i - 1], x)
print(x)


def find_msb(n):
	pos = 0
	while n != 1:
		n = n // 2
		pos += 1
	return pos

def main():
	n = int(input())
	a = []
	for i in range(n):
		a.append(int(input()))
	pos = find_msb(max(a))
	current_val = 0
	for i in range(pos, -1, -1):
		count = 0
		temp = current_val + 2 ** i
		for j in a:
			if temp & j == temp:
				count += 1
		if count >= 2:
			current_val = temp
	print(current_val)
main()


n = int(input())
a = []
v = 0
new = []
while n:
	a.append(int(input()))
	n -= 1
for i in a:
	if i > v:
		for j in new:
			if i & j > v:
				v = i & j
		new.append(i)
print(v)


import sys
n = int(input())
s = []
for i in range(n):
	s.append(int(input()))
large_values = []
value = 0
for num in s:
	if num > value:
		for m in large_values:
			if m & num > value:
				value = m & num
		large_values.append(num)
print(value)


l = []
for _ in range(int(input())):
	l.append(int(input()))
l = sorted(l, reverse=True)
m = 0
for i in range(len(l) - 1, 0, -1):
	m = max(m, l[i] & l[i - 1])
print(m)


import math
n = int(input())
l = []
z = []
for i in range(n):
	l.append(int(input()))
l.sort(reverse=True)
ans_2 = 0
ans_1 = 0
for i in range(n):
	if l[i] == 0:
		z.append(0)
	else:
		z.append(math.floor(math.log2(l[i])))
for i in range(1, n):
	if z[i - 1] == z[i]:
		ans_1 = max(ans_1, l[i - 1] & l[i])
	else:
		ans_2 = max(ans_2, l[i - 1] & l[i])
print(max(ans_2, ans_1))


n = int(input())
l = [int(input()) for i in range(n)]
l.sort()
maxx = -1
for i in range(n - 1, 1, -1):
	tmpp = l[i] & l[i - 1]
	if tmpp > maxx:
		maxx = tmpp
print(maxx)


a = int(input())
k = []
for i in range(a):
	k.append(int(input()))
k.sort(reverse=True)
n = 0
for h in range(1, a):
	n = max(k[h] & k[h - 1], n)
print(n)