You are given a list of integers arr and an integer k.
A subsequence of a list is formed by removing zero or more elements without changing the order of the remaining elements.
A subsequence is considered valid if every pair of adjacent elements in that subsequence has a bitwise XOR equal to k.
Determine the length of the longest valid subsequence.
Note that any subsequence of length 1 is valid regardless of k, since it has no adjacent pairs.
Method
int longestValidSubsequence(List<Integer> arr, int k)
arr is the input list of integersk is the required bitwise XOR value for every adjacent pair in the chosen subsequence- return the length of the longest valid subsequence
Constraints
1 ≤ arr.size() ≤ 100,0000 ≤ arr.get(i) ≤ 100,000,0000 ≤ k ≤ 100,000,000
Notes
- A subsequence does not need to be contiguous.
- The relative order of elements must remain the same as in the original list.
- For every adjacent pair
(a, b) in the chosen subsequence, (a ^ b) == k must hold.
- Any single-element subsequence is always valid.
Examples
Example 1
Input: arr = List.of(2, 1, 3, 5, 2), k = 2
Method Call: longestValidSubsequence(arr = List.of(2, 1, 3, 5, 2), k = 2)
Output: 2
Explanation: The subsequence [1, 3] is valid because 1 ^ 3 = 2. No valid subsequence of length greater than 2 exists. For example, [2, 1, 3] is not valid because 2 ^ 1 != 2.
Example 2
Input: arr = List.of(4, 6, 4, 6, 4), k = 2
Method Call: longestValidSubsequence(arr = List.of(4, 6, 4, 6, 4), k = 2)
Output: 5
Explanation: The full subsequence [4, 6, 4, 6, 4] is valid because each adjacent pair has XOR equal to 2: 4 ^ 6 = 2, 6 ^ 4 = 2, 4 ^ 6 = 2, and 6 ^ 4 = 2.
Example 3
Input: arr = List.of(7, 7, 7), k = 0
Method Call: longestValidSubsequence(arr = List.of(7, 7, 7), k = 0)
Output: 3
Explanation: Since 7 ^ 7 = 0, every adjacent pair in [7, 7, 7] satisfies the condition. Therefore, the entire list can be chosen.
Example 4
Input: arr = List.of(5, 8, 10), k = 7
Method Call: longestValidSubsequence(arr = List.of(5, 8, 10), k = 7)
Output: 1
Explanation: No pair of elements can form a valid adjacent pair with XOR equal to 7 while preserving subsequence order. So the longest valid subsequence has length 1.