Count Subarrays with given XOR

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Prefix XOR. If prefix[r] XOR prefix[l-1] = k, then XOR of subarray [l,r] = k. Count pairs.

Algorithm

1Map from prefix_xor -> count. Initialize {0: 1}.
2For each element: prefix_xor ^= element. Count += map[prefix_xor ^ k]. Map[prefix_xor]++.

Common Pitfalls

•Initialize map with {0:1} for empty prefix. For each position, check if (current_xor ^ k) was seen before.

Count Subarrays with given XOR.java

Java

// Approach: Prefix XOR + HashMap. For each prefix XOR, count how many previous prefixes have XOR = (prefixXOR ^ k).
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public long subarrayXor(int arr[], int k) {
        long n = arr.length;
        long prefixxor = 0;
        long cnt = 0;
        HashMap<Long, Long> map = new HashMap<>();
        map.put(0L, 1L);
        for (int i = 0; i < n; i++) {
            prefixxor ^= arr[i];
            long target = prefixxor ^ k;
            cnt += map.getOrDefault(target, 0L);
            map.put(prefixxor, map.getOrDefault(prefixxor, 0L) + 1L);
        }
        
        return cnt;
    }
}

Was this solution helpful?