Given an array of integers and an integer k, determine the length of the longest valid subsequence in the array.
A subsequence is formed by removing zero or more elements from the array without changing the order of the remaining elements. In a valid subsequence, each pair of adjacent elements has bitwise XOR equal to k.
Note that any subsequence of length 1 is valid regardless of the value of k, because there is no pair of adjacent elements in such a subsequence.
Example
n = 5
arr = [2, 1, 3, 5, 2]
k = 2The subsequence [1, 3] is valid because for its adjacent pair we have 1 XOR 3 = 2. There are no other valid subsequences longer than 2. For example, [2, 1, 3] is not valid because 2 XOR 1 != 2.
Function Description
Complete the function maxSubsequenceLength in the editor below.
The function must return the length of the longest valid subsequence of the array, given parameter k.
Parameters
INTEGER n: the size ofarrINTEGER kINTEGER_ARRAY arr
This problem asks for the longest subsequence whose adjacent pairs all satisfy XOR = k while preserving original order. The standard solution is a value-based dynamic programming approach: as you scan the array, keep the best subsequence length ending with each value, and for the current value x, extend the best chain ending at x XOR k. That makes each update O(1), so the whole algorithm runs in linear time. If the value range is bounded, an array can be used; otherwise, a hash map is safer. The final answer is the maximum DP value, with single-element subsequences always valid.
