Header Ads Widget

Longest AND Subarray | codechef solution

Rajnish Tripathi 15:07

 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,…,� 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≤�≤105
  • 1≤�≤109

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








Tags:

Post a Comment

0 Comments