☕ DSA Java Articles

Topics › Arrays › Hard

Count subarrays with given xor K

Hard TUF ID 562 A2ZSDE

Java source ↗ Edit this article ↗

Problem

You are given an integer array nums and an integer k. Count the contiguous subarrays whose bitwise xor of all elements equals k. Subarrays are identified by their index range, so equal-looking subarrays at different positions count separately.

Constraints: 0 ≤ n ≤ 10^5, values and k fit in a 32-bit signed integer. The count can exceed int (up to n(n+1)/2 ≈ 5 × 10^9), so return a long.

Example 1

nums = [4, 2, 2, 6, 4], k = 6
answer = 4

The subarrays [4, 2], [4, 2, 2, 6, 4], [2, 2, 6] and [6] each xor to 6.

Example 2

nums = [5, 6, 7, 8, 9], k = 5
answer = 2

[5] and [5, 6, 7, 8, 9] (5 ^ 6 ^ 7 ^ 8 ^ 9 = 5).

Approach 1: Brute force

Intuition. Fix the start i, extend to the right one element at a time, and keep the running xor. Whenever it equals k, count one subarray. Because xor of a range can be updated incrementally (xr ^= nums[j]), there is no need for a third loop.

Algorithm.

  1. For each i, set xr = 0.
  2. For each j ≥ i, xr ^= nums[j]; if xr == k, increment the count.
  3. Return the count.
static long bruteForce(int[] nums, int k) {
    long count = 0;
    for (int i = 0; i < nums.length; i++) {
        int xr = 0;
        for (int j = i; j < nums.length; j++) {
            xr ^= nums[j];
            if (xr == k) count++;
        }
    }
    return count;
}

Complexity. Time O(n^2): every (i, j) pair once. Space O(1).

Unlike sums, xor never overflows, so int is fine for xr. Only the counter needs long.

5 × 10^9 steps for n = 10^5 is too slow; we need to avoid re-examining every start for every end.

Approach 2: Optimal, prefix xor and a frequency map

Intuition. Define the prefix xor X[j] = nums[0] ^ ... ^ nums[j], with X[-1] = 0. Xor is its own inverse (a ^ a = 0), so the xor of nums[i+1 .. j] is X[j] ^ X[i]: the common prefix nums[0 .. i] cancels out. Therefore the subarray nums[i+1 .. j] has xor k exactly when

X[j] ^ X[i] == k      which rearranges to      X[i] == X[j] ^ k

So at position j the question becomes: how many earlier prefixes equal X[j] ^ k? A hash map from prefix value to how many times it has occurred answers that in constant time. Add that frequency to the answer, then record X[j] for later positions. Seed the map with 0 → 1 for the empty prefix so that subarrays starting at index 0 are counted.

This is the same shape as counting subarrays with a given sum, with - replaced by ^ because xor undoes itself.

Algorithm.

  1. freq = {0 → 1}, xr = 0, count = 0.
  2. For each element x: xr ^= x; count += freq[xr ^ k]; freq[xr]++.
  3. Return count.
static long optimal(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    freq.put(0, 1);                                  // the empty prefix has xor 0
    int xr = 0;
    long count = 0;
    for (int x : nums) {
        xr ^= x;
        count += freq.getOrDefault(xr ^ k, 0);       // earlier prefixes p with p ^ xr == k
        freq.merge(xr, 1, Integer::sum);
    }
    return count;
}

Dry run on nums = [4, 2, 2, 6, 4], k = 6:

x xr after xr ^ k freq[xr ^ k] count freq after
4 4 2 0 0 {0:1, 4:1}
2 6 0 1 1 {0:1, 4:1, 6:1}
2 4 2 0 1 {0:1, 4:2, 6:1}
6 2 4 2 3 {0:1, 4:2, 6:1, 2:1}
4 6 0 1 4 {0:1, 4:2, 6:2, 2:1}

The two hits at the fourth step are the prefixes with xor 4 ending at indices 0 and 2, i.e. subarrays [2, 2, 6] and [6].

Complexity. Time O(n): one pass, constant-time map operations on average. Space O(n) for the map.

Order matters in the loop body: query before inserting the current prefix. If k == 0, inserting first would make every position count itself (xr ^ 0 == xr), inflating the answer by n.

Edge cases and pitfalls