You are given an array \(A\) having \(N\) integers and an integer \(X\). Find the length of the longest non-empty subsequence of the array \(A\) such that the Bitwise AND of the elements of the subsequence is greater than or equal to \(X\). Print \(-1\) if no such subsequence exists.
A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.
Input format
- The first line of input contains an integer \(T\) denoting the number of test cases. The description of each test case is as follows:
- The first line of each test case contains two integers \(N\) and \(X\).
- The second line of each test case contains \(N\) integers \(A_1, A_2,\dots, A_N\).
Output format
For each test case, print \(-1\) if no subsequence satisfies the given condition. Otherwise, print the length of the longest non-empty subsequence in a separate line.
Constraints
3 3 2 1 2 3 5 3 6 1 7 4 3 3 5 1 3 4
2 3 -1
- In the first test case, it is optimal to take \(A_2, A_3\) in the chosen subsequence because \(A_2 \; \&\; A_3 = 2 \; \& \; 3 = 2 \ge X = 2\).
- In the second test case, it is optimal to take in the chosen subsequence because \(A_1 \; \& \; A_3 \; \&\; A_3 = 6 \; \& \; 7 \; \& \; 4 = 4 \ge X = 3\).
- In the third test case, it is impossible to choose any non-empty subsequence that satisfies the given conditions.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor