Explorer
Data Structures & Algorithms

Find number of subarrays having bitwise XOR equal to K using prefix XOR and hashing.

Problem Statement

Given an array of integers `arr` and an integer `k`, return the total number of subarrays having bitwise XOR of their elements equal to `k`.

Examples

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

Output: 4

Explanation: Subarrays with XOR 6: [4, 2], [4, 2, 2, 6, 4], [2, 2, 6], [6].

Input: arr = [5, 6, 7, 8, 9], k = 5

Output: 2

Explanation: Combining the input according to Count subarrays with given xor K logic yields 2.

Complexity

Time Complexity: O(N)

Space Complexity: O(N)

Hints

šŸ’” Hint 1: Use the mathematical XOR property: if xr ^ y = k, then xr ^ k = y. šŸ’” Hint 2: Maintain a running prefix XOR and a hash map of prefix XOR frequencies. šŸ’” Hint 3: Base case: map.set(0, 1) accounts for prefix XOR of 0 at index -1.

Editorial & Approach

Problem Overview & Intuition

If the prefix XOR up to index i is xr, and we need a subarray XOR of k, we require a previous prefix XOR y such that xr ^ y = k. By XORing both sides with k, we get y = xr ^ k. A hash map provides O(1) frequency lookups.

Step-by-Step Approach

  1. Initialize count = 0, currentXor = 0, map = new Map([[0, 1]]).
  2. Iterate through arr, updating currentXor ^= num.
  3. Compute needed = currentXor ^ k.
  4. If map.has(needed), add its frequency to count.
  5. Increment frequency of currentXor in the map.
  6. Return count.

Optimal Implementation (JavaScript)

function subarraysWithXorK(arr, k) {
  let count = 0, currentXor = 0;
  const map = new Map([[0, 1]]);
  for (let num of arr) {
    currentXor ^= num;
    const needed = currentXor ^ k;
    if (map.has(needed)) count += map.get(needed);
    map.set(currentXor, (map.get(currentXor) || 0) + 1);
  }
  return count;
}

Complexity Analysis

Time Complexity O(N) ā€” single pass with O(1) hash map operations.
Space Complexity O(N) ā€” map of prefix XOR frequencies.

Edge Cases & Corner Traps Handled

  • k is 0: counts subarrays with all duplicate bits canceling.
  • No valid subarray: returns 0.

Count subarrays with given xor K

Hard
Given an array of integers `arr` and an integer `k`, return the total number of subarrays having bitwise XOR of their elements equal to `k`.
Example Scenarios
1Example 1
Input: arr = [4, 2, 2, 6, 4], k = 6
Output: 4
Explanation:

Subarrays with XOR 6: [4, 2], [4, 2, 2, 6, 4], [2, 2, 6], [6].

2Example 2
Input: arr = [5, 6, 7, 8, 9], k = 5
Output: 2
Explanation:

Combining the input according to Count subarrays with given xor K logic yields 2.

Editor
Loading Editor...
arr =
[4, 2, 2, 6, 4]
k =
6
Output:Click "Run" above to execute and verify your code here.
4