Page Contents
Longest AND Subarray October Long Challenge
You are given an integer NN. Consider the sequence containing the integers 1,2,…,N1,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.
Input Format
- The first line contains TT denoting the number of test cases. Then the test cases follow.
- Each test case contains a single integer NN 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≤1051≤T≤105
- 1≤N≤1091≤N≤109
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
Test case 11: The only possible subarray we can choose is [1][1].
Test case 22: We can’t take the entire sequence [1,2][1,2] as a subarray because the bitwise AND of 11 and 22 is zero. We can take either [1][1] or [2][2] as a subarray.
Test case 44: It is optimal to take the subarray [2,3][2,3] and the bitwise AND of 22 and 33 is 22.
Test case 55: It is optimal to take the subarray [4,5,6,7][4,5,6,7] and the bitwise AND of all integers in this subarray is 44.
CLICK BELOW!!
Solution
Program 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))
October Long Challenge 2021
- Longest AND Subarray
- MEX-OR
- Digit Removal
- Yet another MEX problem
- Characteristic Polynomial Verification
- Chef at the Olympics
- Which Mixture
- Three Boxes