AlgoViz
HomeArrays & Hashing

Count subarrays with given xor K

Hard

The same prefix trick, with XOR instead of sum

Problem

Given an array of integers nums and an integer k, return the total number of subarrays whose XOR equals to k.

In simple words

Track prefix XORs; each time prefix-XOR-with-k was seen before, that many subarrays end here with XOR k.

The idea

XOR has the same cancelling property that sums have subtraction: if the prefix XOR up to j is x, then a subarray ending at j has XOR k exactly when some earlier prefix equals x ^ k. Counting occurrences of each prefix XOR turns it into one pass.

The trick

  • Look up prefix ^ k, not prefix - k.
  • Seed the map with {0: 1} for subarrays starting at index 0.
  • O(n) time and space.
4
2
2
6
4
0
1
2
3
4
k6

Step 1 of 17. Brute force: XOR every subarray, count those equal to 6. Values: 4, 2, 2, 6, 4. k 6.

1/17
Brute force
timeO(n²)spaceO(1)

XOR every subarray.

1for (let i = 0; i < n; i++) {2  let x = 0;3  for (let j = i; j < n; j++) { x ^= nums[j]; if (x === k) count++; }4}

Input

array
[4, 2, 2, 6, 4]

Memory

k
6

Output

count
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [4, 2, 2, 6, 4], k = 6
Output:
4
Explanation:
4 subarrays XOR to 6.

Example 2

Input:
nums = [5, 6, 7, 8, 9], k = 5
Output:
2
Explanation:
2 subarrays XOR to 5.

Example 3

Input:
nums = [1, 1], k = 0
Output:
1
Explanation:
[1,1] XORs to 0 → 1 subarray.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.