Longest AND Subarray | CodeChef Solution

Hello coders, today we are going to solve Longest AND Subarray CodeChef Solution whose Problem Code is ANDSUBAR.

Task

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.

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⁵
• 1 ≤ N ≤ 10⁹

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: 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.

Solution – Longest AND Subarray | CodeChef Solution

C++

#include <bits/stdc++.h>
using namespace std;

int setbits(int n){
    int ans = 0;
    while (n > 0){
        ans++;
        n = n >> 1;
    }
    return ans;
}

int main() {
	// your code goes here
	int test;
	cin >> test;
	
	while (test--){
	    int N;
	    cin >> N;
	    
	    int n = setbits(N);
	    int ans1 = N - pow(2, n - 1) + 1;
	    int ans2 = pow(2, n - 1) - pow(2, n - 2);
	    cout << max(ans1, ans2) << endl;
	}
	return 0;
}

Python

Java

Disclaimer: The above Problem (Longest AND Subarray) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Eudcational and Learning Purpose.