Bitwise XOR Subsequences
Updated
Problem statement
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
maxSubsequenceLength(n: int, arr: int[], k: int) → int
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):
int n: the size ofarrint arr[n]: an array of integersint 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.
Examples
Example 1
n = 5arr = [2, 1, 3, 5, 2]k = 2return = 2
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
- 1 <= n <= 10^5
- 0 <= arr[i] <= 10^6
- 0 <= k <= 10^6
- ~ constriants added on 03-13-2025 :)
More Goldman Sachs interview questions
- House Robber IIIPHONE SCREEN · Seen Nov 2026
- Knight Probability in ChessboardONSITE INTERVIEW · Seen Nov 2026
- Trapping Rain WaterPHONE SCREEN · Seen Nov 2026
- Maximum Ones After K OperationsOA · Seen Nov 2026
- Palindrome CounterOA · Seen Oct 2026
- Longest Palindromic SubsequenceOA · Seen Oct 2026
- Best Average Student ScorePHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Check a Complete Binary TreePHONE SCREEN · Seen Oct 2026
- Meeting RoomsPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Minimum Meeting Rooms Without a Sweep LineONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Bitwise XOR SubsequencesJP Morgan Chase · OAJP Morgan Chase interview questions
- Optimize Discount Selection Under a Point BudgetPalantir · OAPalantir interview questions
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Maximum Points by Deleting ElementsIBM · OAIBM interview questions
- Vehicle Builds for Required Terrain (Game Adaptation)Roblox · OARoblox interview questions
- Maximum Points by Deleting ElementsWalmart · OAWalmart interview questions
- Count Valid Bitwise PairsStripe · OAStripe interview questions
- Get Maximum ScoreAtlassian · OAAtlassian interview questions
- Count Subarrays With Given XORInMobi · OAInMobi interview questions
- Longest Common Contiguous String SequenceIntuit · OAIntuit interview questions