DSA interview question

Count Subarrays with XOR K

Hard · Algorithms · Topics: array, prefix xor, hash map

The problem

A network engineer is checking packet checksums: each packet carries an integer, and a known corruption pattern shows up as a contiguous run of packets whose XOR equals a specific value K. The task is to count how many such runs exist in a capture. Checking every subarray is O(n²). XOR behaves like addition for prefix sums, with one bonus: it is its own inverse. The XOR of a[j+1..i] is prefix[i] ^ prefix[j], so a subarray ending at i has XOR K exactly when some earlier prefix equals prefix[i] ^ K. A hash map of prefix-XOR counts makes this O(n).

Example: [4, 2, 2, 6, 4], K = 6 → 4.

Function signature

long long countSubarraysWithXor(const vector<int>& a, int k);

Test cases

Input `(a, k)`	Output	Explanation
`([4, 2, 2, 6, 4], 6)`	4	`[4, 2]`, `[4, 2, 2, 6, 4]`, `[2, 2, 6]`, `[6]`
`([5, 6, 7, 8, 9], 5)`	2	`[5]` and the whole array
`([1, 1, 1], 1)`	4	Each single `[1]`, plus `[1, 1, 1]`
`([0, 0], 0)`	3	`[0]`, `[0]`, `[0, 0]`
`([3], 3)`	1
`([1, 2, 3], 7)`	0

(Confirm: values are non-negative integers; count every (start, end) pair whose XOR is k.)

How interviewers phrase it

"Count the number of subarrays whose XOR equals K" (GeeksforGeeks, InterviewBit).
Asked after "count subarrays with sum K", to check that you can transfer the prefix technique to another operation.

Clarifying questions to ask

Are values non-negative? (XOR is defined on bit patterns either way.)
Count, or list the subarrays?
How large can n be? (The count can reach about n²/2.)

Follow-ups to expect

"Why does prefix[i] ^ prefix[j] give the XOR of a[j+1..i]?"
"How do you find the needed earlier prefix?"
"Why seed the map with {0: 1}?"
"How is this different from the sum version?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview