Longest AND Subarray | codechef solution

Problem

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

You are given an integer $�$. Consider the sequence containing the integers $1,2,\dots ,�$ 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 $�$ denoting the number of test cases. Then the test cases follow.
• Each test case contains a single integer $�$ 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\le �\le 1{0}^{5}$
• $1\le �\le 1{0}^{9}$

• Subtask 1 (100 points): Original constraints

Sample 1:

Input
Output
5
1
2
3
4
7
1
1
2
2
4

Explanation:

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

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

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

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

Code(Python):

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)))

Code(C++):-

#include <iostream>
#include <cmath>
using namespace std;

int main() {
int T;
long N;
cin >>T;
while (T--){
cin >> N;
int bits= floor(log2(N))+1;
int ans =max(N-pow(2,bits-1)+1,pow(2,bits-2));
cout << ans<<"\n";

}
return 0;
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-