<\/span><\/h2>\n\n\n\nYou are given an integer N<\/em><\/strong>. Consider the sequence containing the integers 1, 2, . . . , N<\/strong> 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<\/strong>.<\/p>\n\n\n\n<\/span>Input Format<\/strong><\/span><\/h2>\n\n\n\n- The first line contains T<\/em><\/strong> denoting the number of test cases. Then the test cases follow.<\/li>
- Each test case contains a single integer N <\/em><\/strong>on a single line.<\/li><\/ul>\n\n\n\n
<\/span>Output Format<\/strong><\/span><\/h2>\n\n\n\nFor each test case, output on a single line the length of the longest subarray that satisfy the given property.<\/p>\n\n\n\n
<\/span>Constraints<\/strong><\/span><\/h2>\n\n\n\n- 1 \u2264 T \u2264 105<\/sup><\/strong><\/li>
- 1 \u2264 N \u2264 109<\/sup><\/strong><\/li><\/ul>\n\n\n\n
Subtasks<\/strong><\/p>\n\n\n\nSubtask 1 (100 points):<\/strong> Original constraints<\/p>\n\n\n\nSample Input 1<\/strong><\/p>\n\n\n\n5\n1\n2\n3\n4\n7\n<\/code><\/pre>\n\n\n\nSample Output 1<\/strong><\/p>\n\n\n\n1\n1\n2\n2\n4\n<\/code><\/pre>\n\n\n\nExplanation<\/strong><\/p>\n\n\n\nTest case 1:<\/strong> The only possible subarray we can choose is [1]<\/strong>.<\/p>\n\n\n\nTest case 2:<\/strong> We can’t take the entire sequence [1,2]<\/strong> as a subarray because the bitwise AND of 1<\/strong> and 2<\/strong> is zero. We can take either [1]<\/strong> or [2]<\/strong> as a subarray.<\/p>\n\n\n\nTest case 4:<\/strong> It is optimal to take the subarray [2,3]<\/strong> and the bitwise AND of 2<\/strong> and 3<\/strong> is 2<\/strong>.<\/p>\n\n\n\nTest case 5:<\/strong> It is optimal to take the subarray [4,5,6,7]<\/strong> and the bitwise AND of all integers in this subarray is 4<\/strong>.<\/p>\n\n\n\n<\/span>Solution – Longest AND Subarray | CodeChef Solution<\/strong><\/span><\/h2>\n\n\n\n<\/span>C++<\/strong><\/span><\/h3>\n\n\n\n#include <bits\/stdc++.h>\nusing namespace std;\n\nint setbits(int n){\n int ans = 0;\n while (n > 0){\n ans++;\n n = n >> 1;\n }\n return ans;\n}\n\nint main() {\n\t\/\/ your code goes here\n\tint test;\n\tcin >> test;\n\t\n\twhile (test--){\n\t int N;\n\t cin >> N;\n\t \n\t int n = setbits(N);\n\t int ans1 = N - pow(2, n - 1) + 1;\n\t int ans2 = pow(2, n - 1) - pow(2, n - 2);\n\t cout << max(ans1, ans2) << endl;\n\t}\n\treturn 0;\n}\n<\/pre>\n\n\n\n