Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Count Subarrays with XOR K

Medium · Arrays · Asked at Amazon, Flipkart, Microsoft, Codenation

Print the number of subarrays whose bitwise XOR of all elements equals k.

Input

First line: n k. Second line: n integers.

Output

The number of such subarrays.

Constraints

Prefix XOR: the subarray (j, i] has XOR k exactly when px[j] = px[i] ^ k. Count earlier prefixes in a hash map.

Example 1

Input

5 6
4 2 2 6 4

Output

4

Example 2

Input

5 5
5 6 7 8 9

Output

2

Hints

  1. XOR of a[j+1..i] = px[i] ^ px[j], where px is the prefix XOR.
  2. So for each i you need the number of earlier prefixes equal to px[i] ^ k — keep counts in a hash map (start with px = 0 seen once).

Approach

Same idea as "subarray sum equals K", with XOR instead of sums. Walk the array keeping the running prefix XOR x. Every earlier prefix p with p = x ^ k ends a valid subarray at the current index, so add count[x ^ k], then record x. Initialise count[0] = 1 for subarrays starting at index 0.

Complexity: O(n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;
    unordered_map<long long, long long> cnt;
    cnt[0] = 1;
    long long x = 0, ans = 0, v;
    for (int i = 0; i < n; i++) {
        cin >> v;
        x ^= v;
        auto it = cnt.find(x ^ k);
        if (it != cnt.end()) ans += it->second;
        cnt[x]++;
    }
    cout << ans << "\n";
    return 0;
}

Python solution

import sys
from collections import defaultdict

data = list(map(int, sys.stdin.read().split()))
n, k, a = data[0], data[1], data[2:]
cnt = defaultdict(int)
cnt[0] = 1
x = ans = 0
for v in a:
    x ^= v
    ans += cnt[x ^ k]
    cnt[x] += 1
print(ans)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        HashMap<Long, Long> cnt = new HashMap<>();
        cnt.put(0L, 1L);
        long x = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            x ^= sc.nextLong();
            ans += cnt.getOrDefault(x ^ k, 0L);
            cnt.merge(x, 1L, Long::sum);
        }
        System.out.println(ans);
    }
}

Solve Count Subarrays with XOR K online · All practice problems