Arrays and Hashing Prefix sums
82. Count Subarrays with Given XOR K
You are given an array of non-negative integers nums and an integer k. Return the number of subarrays
whose elements XOR to exactly k.
A subarray is a contiguous sequence of elements from nums. Two subarrays are different if they start or
end at different positions.
The XOR of two numbers (^ in most languages) compares them digit by digit in binary: each digit of the
result is 1 where the two numbers differ and 0 where they agree. The XOR of a subarray is the XOR of all its
elements, for example 5 ^ 3 ^ 6 = 0.
Example 1
Input: nums = [5, 3, 6, 1, 7], k = 6
4Explanation: Four subarrays XOR to 6: [6], [5, 3], [1, 7] and the whole array, because 5 ^ 3 ^ 6 = 0 and
then 0 ^ 1 ^ 7 = 6.
Example 2
Input: nums = [2, 2, 2], k = 2
4Explanation: Each of the three single elements is 2, and so is the whole array: 2 ^ 2 = 0, then 0 ^ 2 = 2. The
two pairs XOR to 0.
Example 3
Input: nums = [7, 7, 1, 1], k = 0
3Explanation: [7, 7], [1, 1] and the whole array XOR to 0, because a number XORed with itself is 0. No single
element is 0 here.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 1050 ≤ nums[i] ≤ 1090 ≤ k ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.