Longest AND Subarray Solution - Codechef

Video Approch:

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

You are given an integer N$N$. Consider the sequence containing the integers 1,2,…,N$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$T$ denoting the number of test cases. Then the test cases follow.
• Each test case contains a single integer N$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≤105$1\le T\le {10}^5$
• 1≤N≤109$1\le N\le {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

Test case 1$1$: The only possible subarray we can choose is [1]$[1]$.

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

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

Test case 5$5$: 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 4$4$.

Longest AND Subarray Solution: 

#include <bits/stdc++.h>

using namespace std;

int main() {

// your code goes here

int t;

cin>>t;

while(t--){

    int n;

    cin>>n;

    

    int setBit = 0;

    int b = n;

    while(b>0){

        setBit ++;

        b = b>>1;

    }

    int A1 = n - pow(2,setBit-1) + 1;

    int A2 = pow(2, setBit-1) - pow(2, setBit-2);

    int ans = max(A1, A2);

    cout<<ans<<endl;

}

return 0;

}