Table of Contents
Longest AND Subarray Solution
You are given an integer N. Consider the sequence containing the integers 1,2,…,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.
- 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.
For each test case, output on a single line the length of the longest subarray that satisfy the given property.
- Subtask 1 (100 points): Original constraints
Sample Input 1
5 1 2 3 4 7
Sample Output 1
1 1 2 2 4
Test case 1: The only possible subarray we can choose is .
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  or  as a subarray.
Test case 3: It is optimal to take the subarray [2,3] and the bitwise AND of 2 and 3 is 2.
Test case 4: It is optimal to take the subarray [4,5,6,7] and the bitwise AND of all integers in this subarray is 4.
Program Python: Longest AND Subarray Solution in Python
for _ in range(int(input())): n=int(input()) if n==1: print(1) continue tmp=1 while(tmp*2<=n): tmp*=2 st=n-tmp+1 if n==tmp: print(tmp//2) else: print(max(st,tmp//2))