Header Ads Widget

Longest AND Subarray | codechef solution

 Problem

Read problem statements in BengaliMandarin ChineseRussian, and Vietnamese as well.

You are given an integer . Consider the sequence containing the integers 1,2,, 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

  • 1105
  • 1109

Subtasks

  • 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 [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.

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

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-