FastPrepBitwise XOR Subsequences
Problems/Bitwise XOR Subsequences

Bitwise XOR Subsequences

Goldman Sachs logoGoldman Sachs● MediumFULLTIMEOA

Updated Sep 2026

QuestionFunctionExamplesConstraints

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):

  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.

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
All Goldman Sachs interview questionsSee Goldman Sachs hiring insights
Saved
class Solution {
    public int maxSubsequenceLength(int n, int[] arr, int k) {
      // write your code here
    }

}
Checking account…