FastPrepFastPrep
Problem Brief

Bitwise XOR Subsequences

FULLTIMEOA

A subsequence of an array is formed by removing zero or more elements from an array without changing the order of the remaining elements. In a valid subsequence, each pair of adjacent elements of the subsequence 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.

Given an array of integers and integer k, determine the length of the longest valid subsequence in the array.

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.

maxSubsequenceLength has the following parameter(s):

  1. int n: the size of arr
  2. int arr[n]: an array of integers
  3. int k: an integer

Constraints

  • 1 ≤ n ≤ 10^5
  • 0 ≤ arr[i] ≤ 10^6
  • 0 ≤ k ≤ 10^6

Input Formatting

In the first line, there is a single integer, n, the number of elements in arr.
Each of the following n lines contains a single integer, arr[i].
In the last line, there is a single integer, k, the value the bitwise XOR of adjacent elements must equal for the subsequence to be valid.

1Example 1

Input
n = 5, arr = [2, 1, 3, 5, 2], k = 2
Output
2
Explanation

The subsequence [1,3] is valid because for all pairs of adjacent elements it has (1 and 3), the bitwise XOR of such elements is equal to k (1 XOR 3 = 2). There are no other valid subsequences that are longer than 2. For example, subsequence [2,1,3] is not valid because 2 XOR 1 does not equal 2.

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= n <= 10^5
  • 0 <= arr[i] <= 10^6
  • 0 <= k <= 10^6
  • ~ constriants added on 03-13-2025 :)
    • public int maxSubsequenceLength(int n, int[] arr, int k) {
  // write your code here
}
    Input

    n

    5

    arr

    [2, 1, 3, 5, 2]

    k

    2

    Output

    2

    Sign in to submit your solution.