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

You are given an integer N. Consider the sequence containing the integers 1, 2, \dots, N in increasing order (each exactly once). Find the length of the longest subarray in this sequence such that the [bitwise AND] of all elements in the subarray is positive.

------ 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 N on a single line.

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

For each test case, output on a single line the length of the longest subarray that satisfy the given property.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{9}$

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

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
5
1
2
3
4
7
----- Sample Output 1 ------ 
1
1
2
2
4
----- explanation 1 ------ 
Test case $1$: The only possible subarray we can choose is $[1]$. 

Test case $2$: We can't take the entire sequence $[1, 2]$ as a subarray because the bitwise AND of $1$ and $2$ is zero. We can take either $[1]$ or $[2]$ as a subarray.  

Test case $4$: It is optimal to take the subarray $[2, 3]$ and the bitwise AND of $2$ and $3$ is $2$.

Test case $5$: It is optimal to take the subarray $[4, 5, 6, 7]$ and the bitwise AND of all integers in this subarray is $4$.

Difficulty: MEDIUM
Tags: Bit manipulation

Constructive algorithms

Number theory

Mathematics

Ad-hoc
Skill types: Bit manipulation

Starter code:

Solutions:
t = int(input())
for z in range(t):
	n = int(input())
	i = 0
	while n >= 2 ** i:
		i += 1
	if i == 1:
		print(1)
	elif n - 2 ** (i - 1) + 1 > 2 ** (i - 2):
		print(n - 2 ** (i - 1) + 1)
	else:
		print(2 ** (i - 2))


for _ in range(int(input())):
	n = int(input())
	ans = 0
	temp = 1
	for i in range(31, -1, -1):
		if n >> i & 1 == 1:
			ans = 1 << i
			if i != 0:
				temp = 1 << i - 1
			break
	print(max(n - ans + 1, temp))


import math
for _ in range(int(input())):
	n = int(input())
	p = int(math.log2(n))
	if n - 2 ** p + 1 >= 2 ** (p - 1):
		print(n - 2 ** p + 1)
	else:
		print(2 ** (p - 1))


import math

def Power(n):
	(ans, x) = (1, 2)
	while n != 0:
		if n & 1 == 1:
			ans = ans * x
		x = x * x
		ans = ans >> 1
	return ans
for _ in range(int(input())):
	n = int(input())
	ans = 0
	temp = 1
	for i in range(31, -1, -1):
		if n >> i & 1 == 1:
			ans = 1 << i
			if i != 0:
				temp = 1 << i - 1
			break
	print(max(n - ans + 1, temp))


t = int(input())
for i in range(t):
	n = int(input())
	if n <= 2:
		print(1)
	elif n >= 3 and n <= 5:
		print(2)
	else:
		l = len(bin(n)[2:])
		print(max(pow(2, l - 2), n - pow(2, l - 1) + 1))


def twopow(a):
	k = 0
	while a != 1:
		a = a // 2
		k += 1
	return 2 ** k
for _ in range(int(input())):
	a = int(input())
	k = twopow(a)
	print(max(1 + a - k, k - k // 2))


for t in range(int(input())):
	n = int(input())
	if n < 3:
		print(1)
	else:
		a = bin(n)[2:]
		m = len(a)
		p = n - 2 ** (m - 1) + 1
		q = 2 ** (m - 1) - 2 ** (m - 2)
		print(max([p, q]))


for _ in range(int(input())):
	x = int(input())
	i = 1
	while i * 2 <= x:
		i = i * 2
	a = x - i + 1
	b = i // 2
	print(max(a, b))


from math import log
for i in range(int(input())):
	n = int(input())
	k = int(log(n, 2))
	if n == 1:
		print(1)
	elif n - 2 ** k == 0:
		print(2 ** (k - 1))
	elif n - 2 ** k >= 2 ** (k - 1):
		print(n - 2 ** k + 1)
	else:
		print(2 ** (k - 1))


from math import log, floor

def func(n):
	return floor(log(n, 2))
for _ in range(int(input())):
	n = int(input())
	if n <= 2:
		print(1)
		continue
	print(max(n - 2 ** func(n) + 1, 2 ** func(n) - 2 ** (func(n) - 1)))


tc = int(input())
for t in range(tc):
	n = int(input())
	ans = 1
	while ans * 2 <= n:
		ans = ans * 2
	ans1 = n - ans + 1
	ans2 = ans // 2
	print(max(ans1, ans2))


def longest_bitwise_and_sequence_length(n):
	m = len(bin(n)[2:]) - 1
	lower_count = 2 ** (m - 1)
	upper_count = n - 2 ** m + 1
	return max(lower_count, upper_count)
for T in range(int(input())):
	print(longest_bitwise_and_sequence_length(int(input())))


import math
for _ in range(int(input())):
	n = int(input())
	ans = 0
	t = 0
	for i in range(32, -1, -1):
		if n >> i & 1 == 1:
			ans = 1 << i
			if i != 0:
				t = 1 << i - 1
			break
	print(max(n - ans + 1, t))


import math as m
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	else:
		power = int(m.log2(n))
		x = 2 ** power // 2
		y = n - 2 ** power + 1
		print(max(x, y))


for _ in range(int(input())):
	N = int(input())
	n = 0
	d = N
	while d != 1:
		d = int(d / 2)
		n += 1
	n = pow(2, n)
	if N <= 2:
		print(1)
	elif N - n + 1 > n / 2:
		print(N - n + 1)
	else:
		print(int(n / 2))


import math
t = int(input())
for i in range(t):
	n = int(input())
	bit = int(math.log2(n)) + 1
	if pow(2, bit) - 1 == n:
		print(pow(2, bit - 1))
	else:
		diff = pow(2, bit) - n
		count1 = pow(2, bit - 1) - diff + 1
		count2 = pow(2, bit - 2)
		if count1 > count2:
			print(count1)
		else:
			print(count2)


def getPowRange(n):
	for i in range(1, 40):
		first = pow(2, i)
		second = pow(2, i + 1)
		if n in range(first, second):
			break
	return i

def calLn(n, i):
	x1 = n - (pow(2, i) - 1)
	x2 = pow(2, i) - 1 - (pow(2, i - 1) - 1)
	mx = max(x1, x2)
	return mx
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(1)
	else:
		pr = getPowRange(n)
		x = calLn(n, pr)
		print(x)


for i in range(int(input())):
	n = int(input())
	if n <= 2:
		print(1)
		continue
	elif n <= 5:
		print(2)
		continue
	b = bin(n)[2:]
	bit = '1' + (len(b) - 1) * '0'
	bitlow = '1' + (len(b) - 2) * '0'
	upper = n + 1 - int(bit, base=2)
	lower = int(bit, base=2) - int(bitlow, base=2)
	print(max(upper, lower))


def solve():
	n = int(input())
	if n == 1 or n == 2:
		return 1
	l = []
	c = 0
	while n > 0:
		if n & 1:
			l.append(1)
		else:
			l.append(0)
		n = n >> 1
		c += 1
	x = pow(2, c - 2)
	ans = 0
	for i in range(len(l) - 1):
		ans += pow(2, i) * l[i]
	return max(x, ans + 1)
for t in range(int(input())):
	x = solve()
	print(x)


import math
for i in range(int(input())):
	n = int(input())
	k = math.floor(math.log(n, 2))
	print(max(n - 2 ** k + 1, 2 ** (k - 1)))


t = int(input())
for _ in range(t):
	n = int(input())
	i = 1
	if n == 1 or n == 2:
		print(1)
		continue
	if n == 3:
		print(2)
		continue
	while i <= n and n > 3:
		i = i * 2
	if i > n:
		i = i / 2
	res = int(max(n - i + 1, i - i / 2))
	print(res)


T = int(input())
for t in range(0, T):
	n = int(input())
	i = 1
	if n == 1 or n == 2:
		print(1)
		continue
	if n == 3:
		print(2)
		continue
	while i <= n and n > 3:
		i = i * 2
	if i > n:
		i = i / 2
	print(int(max(n - i + 1, i - i / 2)))


T = int(input())
for tc in range(T):
	N = int(input())
	mylist = []
	c = 0
	n = 0
	while n < N:
		if N < 2 ** c:
			c = c - 1
			break
		else:
			n = 2 ** c
			c += 1
			mylist.append(n)
	if N + 1 - mylist[-1] > mylist[-1] - mylist[len(mylist) - 2]:
		print(N + 1 - mylist[-1])
	else:
		print(mylist[-1] - mylist[len(mylist) - 2])


t = int(input())
for _ in range(t):
	n = int(input())
	i = 0
	p = 1
	while p <= n:
		p *= 2
		i += 1
	i -= 1
	p = pow(2, i)
	ans = max(p - pow(2, i - 1), n - p + 1)
	print(ans)


import math
tc = int(input().strip())
for t in range(tc):
	n = int(input())
	if n <= 2:
		print(1)
	else:
		a = math.floor(math.log(n, 2))
		section1 = n - 2 ** a + 1
		section2 = 2 ** (a - 1)
		print(max(section1, section2))


for _ in range(int(input())):
	n = int(input())
	ns = 0
	i = 0
	while n - 2 ** i >= 0:
		n -= 2 ** i
		i += 1
	print(max(n, 2 ** (i - 1)))


import math
for i in range(int(input())):
	k = int(input())
	h = math.log(k, 2)
	if h == 0:
		print(1)
	elif h % 1 == 0:
		print(int(2 ** (h - 1)))
	else:
		h = int(h // 1)
		k1 = abs(k - 2 ** h)
		print(int(max(2 ** (h - 1), k1 + 1)))


from math import log
t = int(input())
for i in range(t):
	num = int(input())
	bitPos1 = int(log(num, 2))
	bitPos2 = bitPos1 - 1
	print(max(num - (1 << bitPos1) + 1, 1 << bitPos2 if bitPos2 >= 0 else -1))


import math

def longestANDsubarray(n):
	if n == 1:
		return 1
	bits = int(math.log(n, 2)) + 1
	ans = max(n - pow(2, bits - 1) + 1, pow(2, bits - 2))
	return ans
for _ in range(int(input())):
	n = int(input())
	print(longestANDsubarray(n))


l = [1]
i = 0
j = 0
while i < 1000000001:
	i = pow(2, j)
	l.append(i)
	j += 1
for i in range(int(input())):
	n = int(input())
	for i in range(1, len(l)):
		if n == l[i]:
			print(l[i - 1])
			break
		elif n < l[i]:
			print(max(l[i - 2], n - l[i - 1] + 1))
			break


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(1)
	else:
		for i in range(n):
			if 2 ** i == n:
				print(2 ** i - 2 ** (i - 1))
				break
			elif 2 ** i > n:
				print(max(n - 2 ** (i - 1) + 1, 2 ** (i - 1) - 2 ** (i - 2)))
				break


import math

def Solution(n):
	x = math.floor(math.log(n, 2))
	return max(n + 1 - 2 ** x, 2 ** (x - 1))
test = int(input())
for t in range(test):
	n = int(input())
	print(Solution(n))


t = int(input())
for _ in range(t):
	n = int(input())
	r = 1
	while True:
		r <<= 1
		if r > n:
			n += 1
			break
		if r == n:
			break
	r >>= 1
	rr = r >> 1
	if n - r >= r - rr:
		print(n - r)
	else:
		print(r - rr)


t = int(input())
for i in range(t):
	n = int(input())
	j = 1
	while j <= n:
		a = j
		j = j * 2
	b = n - a + 1
	print(max(a // 2, b))


import math
t = int(input())
for j in range(t):
	n = int(input())
	p = int(math.log(n, 2))
	check = n - 2 ** p + 1
	if n == 1 or n == 2:
		print(1)
		continue
	if check < 2 ** (p - 1):
		print(2 ** (p - 1))
	else:
		print(check)


import math
for t in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		continue
	bits = math.floor(math.log2(n))
	ans = max(n - (1 << bits) + 1, (1 << bits) - 1 - (1 << bits - 1) + 1)
	print(ans)


import math as m
for _ in range(int(input())):
	n = int(input())
	if n <= 2:
		print(1)
	elif n <= 4:
		print(2)
	else:
		l = int(m.log(n, 2))
		print(max(2 ** l - 2 ** (l - 1), n - 2 ** l + 1))


for z in range(int(input())):
	n = int(input())
	(m, val) = (n, 1)
	if n == 1:
		print(1)
	else:
		while m > 1:
			m //= 2
			val *= 2
		print(max(val // 2, n - val + 1))


import math
for i in range(int(input())):
	a = int(input())
	b = int(math.log(a, 2))
	c = max(2 ** b - 2 ** (b - 1), a - 2 ** b + 1)
	print(c)


import math
for _ in range(int(input())):
	n = int(input())
	og = int(math.log(n, 2))
	ans = max(2 ** og - 2 ** (og - 1), n - 2 ** og + 1)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	b = bin(n)[2:]
	bn = len(b)
	if n == 1:
		print(1)
	elif n + 1 - 2 ** (bn - 1) >= 2 ** (bn - 2):
		print(n + 1 - 2 ** (bn - 1))
	else:
		print(2 ** (bn - 2))


import math

def countBits(number):
	return int(math.log(number) / math.log(2) + 1)
t = int(input())
for _ in range(t):
	n = int(input())
	i = countBits(n)
	if n == 1:
		print(1)
	else:
		r = n - 2 ** (i - 1) + 1
		if r > 2 ** (i - 2):
			print(r)
		else:
			print(2 ** (i - 2))


import math
t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print(1)
	else:
		x = math.floor(math.log2(n))
		ans = 2 ** (x - 1)
		anss = n - 2 ** x + 1
		print(max(ans, anss))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(1)
	else:
		x = math.floor(math.log2(n))
		ans1 = 2 ** (x - 1)
		ans2 = n - 2 ** x + 1
		print(max(ans1, ans2))


for q in range(int(input())):
	n = int(input())
	if n <= 2:
		print(1)
		continue
	b = bin(n)[2:]
	l = len(b)
	x = 2 ** (len(b) - 1)
	print(max(n - x + 1, x // 2))


from math import log, floor
for _ in range(int(input())):
	N = int(input())
	if N < 2:
		print(N)
	else:
		b = floor(log(N, 2))
		print(max(N - 2 ** b + 1, 2 ** b - 2 ** (b - 1)))


for _ in range(int(input())):
	x = bin(int(input()))[2:]
	if x.count('1') == len(x):
		print(2 ** (len(x) - 1))
	else:
		diff = int(x, 2) - int('1' + (len(x) - 1) * '0', 2) + 1
		print(max(diff, 2 ** (len(x) - 2)))


from math import log, floor
T = int(input())

def solve(n):
	return floor(log(n, 2))
for x in range(T):
	n = int(input())
	if n <= 2:
		print(1)
	else:
		print(max(n - 2 ** solve(n) + 1, 2 ** solve(n) - 2 ** (solve(n) - 1)))


import math
a = int(input())
for i in range(a):
	n = int(input())
	x = int(math.log(n, 2))
	max3 = n - 2 ** x + 1
	max4 = 2 ** x - 2 ** (x - 1)
	print(max(max3, max4))


from math import log2
t = int(input())
for i in range(t):
	n = int(input())
	rt = int(log2(n))
	if rt == 0:
		print(1)
	else:
		print(max(n - 2 ** rt + 1, 2 ** (rt - 1)))


import math
T = int(input())
for _ in range(T):
	l = []
	n = int(input())
	z = n
	if n % 4 == 0:
		z = n - 1
	x = int(math.log(z, 2))
	a1 = 2 ** x
	b1 = a1 * 2 - 1
	a2 = 2 ** (x - 1)
	b2 = a2 * 2 - 1
	if n <= b1:
		l.append(n - a1 + 1)
	else:
		l.append(b1 - a1 + 1)
	if n <= b2:
		l.append(n - a2 + 1)
	else:
		l.append(b2 - a2 + 1)
	print(max(l))


import math
T = int(input())
for _ in range(T):
	N = int(input())
	MSB = int(math.log2(N))
	X = pow(2, MSB - 1)
	Y = N - pow(2, MSB) + 1
	print(max(X, Y))


for case in range(int(input())):
	N = int(input())
	a = 1
	while 2 * a <= N:
		a *= 2
	print(max(a // 2, N - a + 1))


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = int(math.log(n, 2))
	print(max(n - 2 ** a + 1, 2 ** (a - 1)))


t = int(input())
while t > 0:
	n = int(input())
	s = 0
	while s < n:
		s = s * 2 + 1
	mx = 0
	if n <= 2:
		mx = 1
	elif n <= 4:
		mx = 2
	elif s == n:
		mx = s - s // 2
	else:
		s = s - s // 2 - 1
		mx = max(n - s, s - s // 2)
	print(mx)
	t -= 1