Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

The *MEX* (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

The MEX of [2, 2, 1] is 0, because 0 does not belong to the array.
The MEX of [3, 1, 0, 1] is 2, because 0 and 1 belong to the array, but 2 does not.
The MEX of [0, 3, 1, 2] is 4 because 0, 1, 2 and 3 belong to the array, but 4 does not.

Find the maximum possible MEX of an array of non-negative integers such that the [bitwise OR] of the elements in the array does not exceed X.

------ Input Format ------ 

- The first line contains T denoting the number of test cases. Then the test cases follow.
- Each test case contains a single integer X on a single line.

------ Output Format ------ 

For each test case, output on a single line the maximum possible MEX of the array satisfying the given property.

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

$1 ≤ T ≤ 10^{5}$
$0 ≤ X ≤ 10^{9}$

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
4
0
1
2
5

----- Sample Output 1 ------ 
1
2
2
4

----- explanation 1 ------ 
Test case $1$: The array could be $[0]$. 

Test case $2$: The array could be $[0, 1]$. Here the bitwise OR of $0$ and $1$ is $1$ and the MEX of the array is $2$ as both $0$ and $1$ belongs to the array.

Test case $4$: The array could be $[1, 0, 3, 2]$. Here the bitwise OR of all integers in the array is $3$ and the MEX of the array is $4$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
from math import log2

def calc(num):
	cur = log2(num + 1)
	return cur == int(cur)

def soln(n: int) -> int:
	if calc(n):
		return n + 1
	return 1 << int(log2(n))
for _ in range(int(input())):
	n = int(input())
	print(soln(n))


t = int(input())
for i in range(t):
	x = int(input())
	if x == 0:
		print(1)
	elif x == 1 or x == 2:
		print(2)
	else:
		po = 1
		while 2 * po <= x:
			po *= 2
		if x == 2 * po - 1:
			print(x + 1)
		else:
			print(po)


for t in range(int(input())):
	a = int(input())
	if a > 4:
		k = 0
		l = a
		while a // 2:
			a //= 2
			k += 1
		if 2 * 2 ** k - 1 == l:
			print(l + 1)
		else:
			print(2 ** k)
	else:
		k = 0
		l = 0
		while a >= k:
			l += 1
			k |= l
		print(l)


import math
for _ in range(int(input())):
	x = int(input())
	if x == 0:
		print(1)
	elif x == 1 or x == 2:
		print(2)
	else:
		y = int(math.log2(x + 1))
		print(2 ** y)


import math
t = int(input())
for _ in range(t):
	x = int(input())
	if x == 0:
		print(1)
		continue
	mex = 1
	orArray = 0
	i = 1
	while i <= 2 ** int(math.log2(x) + 1):
		orArray |= i
		if orArray > x:
			mex = i
			break
		i *= 2
	print(mex)


t = int(input())
for i in range(t):
	x = int(input())
	x += 1
	cnt = -1
	while x:
		x = x >> 1
		cnt += 1
	print(2 ** cnt)


from math import floor, log

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
tcs = inp()
for i in range(tcs):
	X = inp()
	X += 1
	count = -1
	while X:
		X = X >> 1
		count += 1
	MEX = 2 ** count
	print(MEX)


import math
for z in range(int(input())):
	x = int(input())
	i = int(math.log(x + 1, 2))
	print(2 ** i)


from bisect import bisect_left, bisect_right
import math
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for i in range(ii()):
	N = ii()
	if N == 0:
		print(1)
	elif N == 1 or N == 2:
		print(2)
	else:
		ans = 1
		f = False
		while ans * 2 <= N:
			ans *= 2
			if ans == N:
				f = True
				print(N)
			elif N == 2 * ans - 1:
				f = True
				print(N + 1)
		if f == False:
			print(ans)


def listin():
	a = list(map(int, input().split()))
	return a
for tastcas in range(int(input())):
	n = int(input())
	x = bin(n)[2:]
	if '0' in x:
		print(int('1' + '0' * (len(x) - 1), 2))
	else:
		print(n + 1)


import math

def main():
	if x == 0:
		print(1)
	elif x == 1:
		print(2)
	else:
		bits = int(math.log2(x))
		if 2 ** (bits + 1) - 1 == x:
			print(2 ** (bits + 1))
		else:
			print(2 ** bits)
t = int(input())
for _ in range(t):
	x = int(input())
	main()


mod = 1000000007

def integer_list():
	return list(map(int, input().split()))

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())
import math
import sys
from collections import Counter
from decimal import Decimal

def main():
	if x == 0:
		print(1)
	elif x == 1:
		print(2)
	else:
		bits = int(math.log2(x))
		if 2 ** (bits + 1) - 1 == x:
			print(2 ** (bits + 1))
		else:
			print(2 ** bits)
t = int(input())
for _ in range(t):
	x = int(input())
	main()


T = int(input(''))
for i in range(T):
	X = int(input(''))
	a = 1
	while a * 2 <= X + 1:
		a *= 2
	print(a)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 0:
		print(1)
	else:
		n2 = int(math.log2(n + 1))
		print(2 ** n2)


import math

def mexor(n):
	p1 = int(math.log(n + 1) / math.log(2))
	p2 = 1 << p1
	print(p2)
q = int(input())
for i in range(q):
	n = int(input())
	mexor(n)


import math
for _ in range(int(input())):
	x = int(input())
	if x == 0 or x == 1:
		print(x + 1)
	elif x & x - 1 == 0:
		print(x)
	else:
		p = int(math.log(x + 1, 2))
		print(int(pow(2, p)))


for _ in range(int(input())):
	n = int(input())
	if n == 0:
		ans = 1
	elif n == 1 or n == 2:
		ans = 2
	else:
		sum = 1
		while 2 * sum <= n:
			sum = sum * 2
			if sum == n:
				ans = n
			elif n == 2 * sum - 1:
				ans = n + 1
			else:
				ans = sum
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	if n == 0:
		print(1)
	elif n == 1 or n == 2:
		print(2)
	else:
		log2 = math.log2(n)
		power2_ = 2 ** int(log2)
		power2 = 2 ** int(log2 + 1)
		if n == power2 - 1:
			print(power2)
		else:
			print(power2_)


t = int(input())
for i in range(t):
	n = int(input())
	i = 1
	sum = 1
	while sum + i * 2 <= n:
		sum = sum + i * 2
		i = i * 2
	if n == 0:
		print(1)
	else:
		print(sum + 1)


import math

def mexOr(x):
	if x & x + 1 == 0:
		return x + 1
	nearestPower = int(math.log(x, 2))
	minAns = 2 ** nearestPower
	return minAns
testCase = int(input())
for i in range(testCase):
	x = int(input())
	print(mexOr(x))


for _ in range(int(input())):
	n = int(input())
	ans = -1
	for i in range(60):
		if 1 << i & n:
			ans = pow(2, i)
	val = '{0:b}'.format(int(n))
	val = val[::-1]
	idx = -1
	for i in range(len(val)):
		if val[i] == '0':
			idx = i
			break
	if n == 0:
		print(1)
		continue
	if n == 1:
		print(2)
		continue
	if idx == -1:
		print(n + 1)
	else:
		print(ans)


def check(N):
	if N == 0:
		return 1
	if N == 1:
		return 2
	pe = 1
	while pe * 2 <= N:
		pe = pe * 2
	if pe == N:
		return N
	if N == pe * 2 - 1:
		return N + 1
	return pe
for _ in range(int(input())):
	N = int(input())
	print(check(N))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if n == 0:
		ans = 1
	elif n == 1 or n == 2:
		ans = 2
	else:
		sum = 1
		while 2 * sum <= n:
			sum = sum * 2
			if sum == n:
				ans = n
			elif n == 2 * sum - 1:
				ans = n + 1
			else:
				ans = sum
	print(ans)


n = int(input())
for i in range(n):
	m = int(input())
	a = True
	c = 0
	x = 0
	x += m
	if x == 0:
		print(1)
	else:
		while x:
			if x % 2 == 0:
				a = False
			x = x // 2
			c += 1
		if a:
			print(m + 1)
		else:
			s = 0
			c = c - 1
			while c:
				c = c - 1
				s = s + 2 ** c
			print(s + 1)


import math
for i in range(int(input())):
	n = int(input())
	p = int(math.log2(n + 1))
	print(2 ** p)


import math
for _ in range(int(input())):
	n = int(input())
	if n == 0:
		print(1)
	elif n == 1:
		print(2)
	else:
		li = int(math.log(n, 2))
		if pow(2, li + 1) - 1 == n:
			print(n + 1)
		else:
			print(pow(2, li))


import math

def solve(n):
	return 2 ** int(math.log2(n + 1))
T = int(input())
for _ in range(T):
	n = list(map(int, input().strip().split()))
	print(solve(n[0]))


def chk(n):
	s = 1
	res = 0
	while 2 * s <= n:
		s *= 2
		if s == n:
			res = n
		elif n == s * 2 - 1:
			res = n + 1
		else:
			res = s
	return res
for i in range(int(input())):
	n = int(input())
	if n <= 0:
		res = 1
	elif n < 3:
		res = 2
	else:
		res = chk(n)
	print(res)


for t in range(int(input())):
	x = int(input())
	if x == 0:
		print(1)
		pass
	elif x == 1 or x == 2:
		print(2)
		pass
	else:
		a = 2
		while a | a - 1 <= x:
			a = a * 2
		print(a)


for _ in range(int(input())):
	x = int(input())
	y = bin(x)[2:]
	if x == 0:
		ans = 1
	elif '0' not in y:
		ans = x + 1
	else:
		L = len(y)
		ans = 2 ** (L - 1)
	print(ans)


dict1 = {0: 0, 1: 1, 2: 3, 4: 7, 8: 15, 16: 31, 32: 63, 64: 127, 128: 255, 256: 511, 512: 1023, 1024: 2047, 2048: 4095, 4096: 8191, 8192: 16383, 16384: 32767, 32768: 65535, 65536: 131071, 131072: 262143, 262144: 524287, 524288: 1048575, 1048576: 2097151, 2097152: 4194303, 4194304: 8388607, 8388608: 16777215, 16777216: 33554431, 33554432: 67108863, 67108864: 134217727, 134217728: 268435455, 268435456: 536870911, 536870912: 1073741823, 1073741824: 2147483647}
for _ in range(int(input())):
	x = int(input())
	for key in dict1:
		if dict1[key] > x:
			print(key)
			break


for _ in range(int(input())):
	n = int(input())
	c = 1
	q = 2
	while n >= q:
		q = q * 2
	p = q // 2
	if n == q - 1:
		print(q)
	else:
		print(p)


for i in range(int(input())):
	X = int(input())
	cur_pow = 1
	while 2 * cur_pow - 1 <= X:
		cur_pow *= 2
	print(cur_pow)


for i in range(int(input())):
	x = int(input())
	if x in [0, 1]:
		print(x + 1)
	else:
		l = 0
		for j in range(1, 34):
			if 2 ** j - 1 > x:
				print(l + 1)
				break
			l = 2 ** j - 1


for i in range(int(input())):
	n = int(input())
	ans = 1
	s = 1
	if n == 0:
		ans = 1
	elif n == 1 or n == 2:
		ans = 2
	else:
		while s * 2 <= n:
			s *= 2
		if s == n:
			ans = n
		elif n == 2 * s - 1:
			ans = n + 1
		else:
			ans = s
	print(ans)


for i in range(int(input())):
	x = int(input())
	if x == 0:
		mex = 1
	ans = 1
	j = 0
	while ans * 2 <= x:
		ans *= 2
		j += 1
	a = ans - 1
	b = 2 ** (j + 1)
	if x in range(a, b - 1):
		mex = ans
	elif x == b - 1:
		mex = b
	print(mex)


for _ in range(int(input())):
	x = int(input())
	if x == 0:
		print(1)
		continue
	if x == 1 or x == 2:
		print(2)
		continue
	temp = 1
	while temp * 2 <= x:
		temp = temp * 2
	if temp == x:
		print(temp)
	elif x == 2 * temp - 1:
		print(x + 1)
	else:
		print(temp)


try:

	def mex(n):
		if n == 0:
			return 1
		if n == 1:
			return 2
		bitN = bin(n).replace('0b', '')
		l = len(bitN)
		bound_num = '1' * l
		while int(bound_num, 2) <= n:
			bound_num += '1'
		return 2 ** (len(bound_num) - 1)
	for _ in range(int(input())):
		print(mex(int(input())))
except:
	pass


import math
a = [0]
x = 0
i = 1
while x <= int(1000000000.0 + 1):
	x |= i
	a.append(x)
	i *= 2
for _ in range(int(input())):
	x = int(input())
	for i in range(len(a)):
		if a[i] > x:
			print(2 ** (i - 1))
			break


from math import log2
for _ in range(int(input())):
	n = int(input())
	pow = int(log2(n + 1))
	powerof2 = 1 << pow
	print(powerof2)


for _ in range(int(input())):
	x = int(input())
	b = bin(x)[2:]
	c = '1' + '0' * (len(b) - 1)
	if x == 0:
		print(1)
	elif x == 1:
		print(2)
	elif all([b[i] == '1' for i in range(len(b))]):
		print(x + 1)
	else:
		print(int(c, 2))


for i in range(int(input())):
	x = int(input())
	s = 1
	u = 2
	while s | u <= x:
		s = s | u
		u = u * 2
	print(1 if not x else u)


t = int(input())
for _ in range(t):
	n = int(input())
	a = 1
	b = 2
	while n >= b | a:
		a = a | b
		b = b << 1
	if n:
		print(b)
	else:
		print('1')


def sol():
	return needed()

def needed():
	return

def mat(X):
	if X:
		low = 2 ** int(log(X, 2))
		if X == low * 2 - 1:
			return 2 * low
		else:
			return low
	else:
		return 1
from math import log
sol()
sol()
sol()
for _ in range(int(input())):
	print(mat(int(input())))


n = int(input())
for i in range(1, n + 1):
	a = int(input())
	if a == 0:
		print(1)
	elif a == 1 or a == 2:
		print(2)
	else:
		temp = 1
		while temp * 2 <= a:
			temp = temp * 2
		if temp == a:
			print(a)
		elif a == 2 * temp - 1:
			print(a + 1)
		else:
			print(temp)


for _ in range(int(input())):
	x = int(input())
	i = 1
	if x == 0:
		print(1)
	elif x == 1 or x == 2:
		print(2)
	else:
		while i * 2 <= x:
			i = i * 2
		if i * 2 - 1 == x:
			print(x + 1)
		elif i == x:
			print(x)
		else:
			print(i)


for i in range(int(input())):
	(n, a, b) = (int(input()), 1, 2)
	while a | b <= n:
		a |= b
		b *= 2
	print(1 if not n else b)


for t in range(int(input())):
	n = int(input())
	a = bin(n).replace('0b', '')
	l = len(a)
	p = 2 ** l
	if n & n - 1 == 0 and n != 1 and (n != 0):
		print(n)
	elif n & n + 1 == 0:
		print(n + 1)
	elif n == 1 or n == 0:
		print(n + 1)
	else:
		print(p // 2)


inp = int(input())
for _ in range(inp):
	num = int(input())
	numb = f'{num:32b}'.strip()
	length = len(numb) - 1
	if '0' in numb:
		print(2 ** length)
	else:
		print(num + 1)


a = [0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591, 17179869183, 34359738367, 68719476735, 137438953471, 274877906943, 549755813887, 1099511627775, 2199023255551, 4398046511103, 8796093022207, 17592186044415, 35184372088831, 70368744177663, 140737488355327, 281474976710655, 562949953421311]
for i in range(int(input())):
	x = int(input())
	i = 0
	while a[i] <= x:
		i += 1
	print(a[i - 1] + 1)


for q in range(int(input())):
	x = int(input())
	s = bin(x).replace('0b', '')
	if 2 ** len(s) == x:
		print(x)
	elif 2 ** len(s) - 1 == x:
		print(x + 1)
	else:
		print(2 ** (len(s) - 1))


import math as mt
t = int(input())
for i in range(t):
	x = int(input())
	y = int(mt.log2(x + 1))
	rs = 1 << y
	print(rs)