logoNEURAL COOK
SearchAll PostsTagsNotesAuthor
logoNEURAL COOK

A posts created with Next.js and Tailwind.css

Explore

  • All posts
  • Notes
  • Snippets
  • Tags
  • RSS feed

Connect

instagramtwitterfacebookyoutubelinkedinmailgithub

© 2026 VIKI. All rights reserved.

Built with
Contents
Table Of Contents
Theory
Subarray Sum Equals KCount Subarrays with Given XOR KLargest Subarray with 0 SumLongest Consecutive SequenceLongest Subarray with Sum K
Code Scratch/take u forward/hashing/faqs

Count Subarrays with Given XOR K

5 min read
On this pageQuestion
QuestionSolutionPatternHow to IdentifyDescriptionThe IntuitionComplexityCodeCaveatsConcepts to Think AboutLogical Follow-up

# Question

Given an array of integers nums and an integer kkk, return the total number of contiguous subarrays whose elements, when XORed together, equal kkk.

# Solution

# Pattern

Prefix XOR with Hash Map (Frequency Map) Maintain a running XOR as you iterate through the array. Store the frequencies of all running XORs seen so far in a Hash Map. At each step, check if the value (current_xor⊕k)(current\_xor \oplus k)(current_xor⊕k) exists in the map; if it does, add its frequency to your total count.

# How to Identify

  • The problem asks for the count of contiguous subarrays.
  • The constraint relies on a binary operation (XOR), similar to prefix sum problems.
  • Sliding Window / Two Pointers cannot be used because XOR operations are not monotonic (adding a number to a subarray can either increase or decrease the XOR value unpredictably).

# Description

Step-by-step explanation:

  1. Create a HashMap to store <PrefixXorValue, Frequency>.
  2. Seed the map with (0, 1). This handles the case where a valid subarray starts exactly at index 0. (Conceptually, the prefix XOR before the array begins is 0).
  3. Initialize currentXor = 0 and count = 0.
  4. Iterate through the array. For each element:
    • Update currentXor = currentXor ^ num.
    • Calculate the required past prefix XOR: targetXor = currentXor ^ k.
    • If targetXor exists in the map, it means there are historical prefixes we can "chop off" to leave a remaining subarray with an XOR of exactly kkk. Add its frequency to count.
    • Update the map by incrementing the frequency of the currentXor.
  5. Return the total count.

# The Intuition

This relies heavily on a fundamental property of the XOR operation: If A⊕B=CA \oplus B = CA⊕B=C, then A⊕C=BA \oplus C = BA⊕C=B.

Let's define:

  • CurrentXorCurrentXorCurrentXor = the XOR of all elements from index 000 to iii.
  • SubarrayXorSubarrayXorSubarrayXor = the XOR of elements in our target subarray (which we want to be kkk).
  • PastXorPastXorPastXor = the XOR of the prefix we need to "remove" or "chop off" to get our subarray.

We know that: PastXor⊕SubarrayXor=CurrentXorPastXor \oplus SubarrayXor = CurrentXorPastXor⊕SubarrayXor=CurrentXor

We want SubarrayXor=kSubarrayXor = kSubarrayXor=k. Substituting this: PastXor⊕k=CurrentXorPastXor \oplus k = CurrentXorPastXor⊕k=CurrentXor

Using the XOR property to solve for PastXorPastXorPastXor: PastXor=CurrentXor⊕kPastXor = CurrentXor \oplus kPastXor=CurrentXor⊕k

Therefore, as we stand at index iii, if we can look back into our Hash Map and find how many times the value (CurrentXor⊕k)(CurrentXor \oplus k)(CurrentXor⊕k) occurred in the past, that is exactly the number of valid subarrays ending at index iii.

# Complexity

LabelWorstAverage
Time ComplexityO(N2)O(N^2)O(N2)O(N)O(N)O(N)
Space ComplexityO(N)O(N)O(N)O(N)O(N)O(N)

# Time Complexity

We iterate through the array of size NNN exactly once. Hash Map lookups and insertions are O(1)O(1)O(1) on average, yielding O(N)O(N)O(N) time. In the absolute worst case (extreme hash collisions), map operations degrade, leading to O(N2)O(N^2)O(N2) time.

# Space Complexity

In the worst case, every running prefix XOR is unique. The Hash Map will store NNN distinct entries, resulting in O(N)O(N)O(N) auxiliary space.

# Code

class Solution {
    public int subarraysWithXorK(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
 
        Map&lt;Integer, Integer&gt; prefixXorFreq = new HashMap<>();
        // Base case: An XOR of 0 has been seen exactly once (conceptually before the array starts)
        prefixXorFreq.put(0, 1);
 
        int currentXor = 0;
        int count = 0;
 
        for (int num : nums) {
            currentXor ^= num;
 
            // Property of XOR: If A ^ B = C, then A ^ C = B
            // Let A = past prefix, B = subarray, C = current prefix
            // We want B = k. Therefore, past prefix A = C ^ k
            int targetXor = currentXor ^ k;
            
            count += prefixXorFreq.getOrDefault(targetXor, 0);
 
            // Add the current prefix XOR to our frequency map
            prefixXorFreq.put(currentXor, prefixXorFreq.getOrDefault(currentXor, 0) + 1);
        }
 
        return count;
    }
}

# Caveats

  • Sliding Window Trap: XOR behaves wildly. 5 ^ 2 = 7, but 7 ^ 1 = 6. Because the value does not strictly increase or decrease, you cannot use a two-pointer sliding window to shrink/expand based on the current XOR value. Prefix Maps are mandatory.
  • Order of Operations: You must evaluate currentXor ^ k and add to the count before inserting the currentXor into the map. If k=0k = 0k=0, inserting first will falsely count the empty subarray (an element XORed with itself is 0).

# Concepts to Think About

  • Isomorphic to Subarray Sum: Notice how this algorithm is character-for-character identical to "Subarray Sum Equals K", simply replacing the + and - operators with ^. Addition and XOR share group-theoretic properties (associativity, identity, inverse) that make prefix algorithms interchangeable between them.
  • Self-Inverse Property: In prefix sum, to remove prefix AAA from prefix CCC, you do C−AC - AC−A. Because XOR is its own inverse, to remove prefix AAA from prefix CCC, you do C⊕AC \oplus AC⊕A.

# Logical Follow-up

Question: What if the problem asked for the longest subarray with XOR kkk? Solution: Instead of storing &lt;PrefixXor, Frequency&gt;, we store &lt;PrefixXor, Earliest_Index&gt;. When we calculate targetXor = currentXor ^ k, we check if it exists in the map. If it does, the length of the subarray is current_index - map.get(targetXor). We track the maximum length found. Time: O(N)O(N)O(N), Space: O(N)O(N)O(N).

Question: Can you solve this using a Trie? Solution: Yes. While a HashMap is standard, you can insert the binary representation of the running XORs into a Trie. When searching for currentXor ^ k, you traverse the Trie. A Trie approach provides a strict O(N⋅32)O(N \cdot 32)O(N⋅32) worst-case time complexity, bypassing the O(N2)O(N^2)O(N2) hash collision worst-case of HashMaps, though it takes more memory and code to write.

←PreviousSubarray Sum Equals KNext→Largest Subarray with 0 Sum

On this page

QuestionSolutionPatternHow to IdentifyDescriptionThe IntuitionComplexityCodeCaveatsConcepts to Think AboutLogical Follow-up