Longest AND Subarray solution codechef-You are given an integer NN

Longest AND Subarray solution codechef

You are given an integer NN. Consider the sequence containing the integers 1,2,,N1,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 Longest AND Subarray solution codechef

  • The first line contains TT denoting the number of test cases. Then the test cases follow.
  • Each test case contains a single integer NN on a single line.

Output Format Longest AND Subarray solution codechef

For each test case, output on a single line the length of the longest subarray that satisfy the given property.

Constraints Longest AND Subarray solution codechef

  • 1T1051≤T≤105
  • 1N1091≤N≤109

Subtasks Longest AND Subarray solution codechef

  • Subtask 1 (100 points): Original constraints

Sample Input 1  Longest AND Subarray solution codechef

5
1
2
3
4
7

Sample Output 1 Longest AND Subarray solution codechef

1
1
2
2
4

Explanation Longest AND Subarray solution codechef

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

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

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

Test case 55: 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 44.

Longest AND Subarray solution codechef

You are given an integer C. Let d be the smallest integer such that 2d is strictly greater than C.

Consider all pairs of non-negative integers (A,B) such that A,B<2d and AB=C ( denotes the bitwise XOR operation). Find the maximum value of AB over all these pairs.

Input Longest AND Subarray solution codechef

  • The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
  • The first and only line of each test case contains a single integer C.

Output Longest AND Subarray solution codechef

For each test case, print a single line containing one integer ― the maximum possible product AB.

Constraints Longest AND Subarray solution codechef

  • 1T105
  • 1C109

Subtasks Longest AND Subarray solution codechef

Subtask #1 (30 points): 1C103

Subtask #2 (70 points): original constraints

Sample Input 1 Longest AND Subarray solution codechef

2
13
10

Sample Output 1 Longest AND Subarray solution codechef

70
91

Explanation Longest AND Subarray solution codechef

Example case 1: The binary representation of 13 is “1101”. We can use A=10 (“1010” in binary) and B=7 (“0111” in binary). This gives us the product 70. No other valid pair (A,B) can give us a larger product.

Example case 2: The binary representation of 10 is “1010”. We can use A=13 (“1101”) and B=7 (“0111”). This gives us the maximum product 91.

Leave a Reply

Your email address will not be published. Required fields are marked *

*