Count Subarrays With Given XOR K

Problem link - https://www.geeksforgeeks.org/problems/count-subarray-with-given-xor/1

One of the most frequently asked hashing problems in interviews is counting the number of subarrays having a given XOR value K.

The brute force solution is straightforward, but the optimal approach uses a beautiful combination of Prefix XOR and HashMap to achieve linear time complexity.

---

Problem Statement

Given an array arr[] and an integer k, count the number of subarrays whose XOR is equal to k.

Example

Input:
arr = [4, 2, 2, 6, 4]
k = 6

Output:
4

Subarrays having XOR = 6:

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

Total count = 4

---

Brute Force Approach

Generate every possible subarray and calculate its XOR.

Interview Explanation

For every starting index, keep extending the subarray towards the right while maintaining the current XOR. Whenever the XOR becomes k, increment the count.

Complexity

• Time Complexity: O(N²)
• Space Complexity: O(1)

Brute Force Code

class Solution {
    public long subarrayXor(int[] arr, int k) {

        long count = 0;

        for (int i = 0; i < arr.length; i++) {

            int xor = 0;

            for (int j = i; j < arr.length; j++) {

                xor ^= arr[j];

                if (xor == k) {
                    count++;
                }
            }
        }

        return count;
    }
}

---

Optimal Approach: Prefix XOR + HashMap

Key Observation

For Sum problems, we use:

prefixSum - k

For XOR problems, we use:

prefixXor ^ k

Suppose:

prefixXor = XOR from index 0 to i

and some previous prefix XOR is:

oldPrefixXor

Then:

oldPrefixXor ^ prefixXor = k

Using XOR properties:

oldPrefixXor = prefixXor ^ k

Therefore, for every index, we simply need to know how many times (prefixXor ^ k) has appeared before.

A HashMap helps us find this frequency in O(1).

---

Why Store Frequency Instead of Index?

The question asks us to:

Count subarrays

not

Find longest subarray

Therefore we store:

prefixXor -> frequency

Every previous occurrence contributes one valid subarray ending at the current index.

---

Dry Run

arr = [4, 2, 2, 6, 4]
k = 6

Initialize:

map = {0 : 1}
xor = 0
count = 0

Index 0

xor = 4
need = 4 ^ 6 = 2

Not found.

Store:

map = {0:1, 4:1}

---

Index 1

xor = 6
need = 6 ^ 6 = 0

Found once.

count = 1

Subarray:

[4, 2]

---

Index 2

xor = 4
need = 4 ^ 6 = 2

Not found.

Store frequency of 4.

---

Index 3

xor = 2
need = 2 ^ 6 = 4

4 exists twice.

count += 2

Subarrays:

[2, 2, 6]
[6]

---

Index 4

xor = 6
need = 6 ^ 6 = 0

0 exists once.

count += 1

Subarray:

[4, 2, 2, 6, 4]

Final answer:

count = 4

---

Optimal Java Solution

class Solution {
    public long subarrayXor(int[] arr, int k) {

        HashMap<Integer, Integer> map = new HashMap<>();

        int xor = 0;
        long count = 0;

        map.put(0, 1);

        for (int num : arr) {

            xor ^= num;

            int need = xor ^ k;

            count += map.getOrDefault(need, 0);

            map.put(xor, map.getOrDefault(xor, 0) + 1);
        }

        return count;
    }
}

---

Complexity Analysis

• Time Complexity: O(N)
• Space Complexity: O(N)

---

Key Takeaway

Whenever you see:

Count subarrays with XOR = K

Think:

oldPrefixXor = currentPrefixXor ^ k

Store prefix XOR frequencies in a HashMap and count matching occurrences in O(N) time.