Subarrays with XOR ‘K’

HashMap<Integer,Integer> xorMap = new HashMap<>();

What the Program Does:

• The program finds how many subarrays in a given list of numbers have an XOR value that matches a target value b.

XOR Basics:

• XOR is a bitwise operation that compares the binary form of two numbers. When the bits are different, the XOR result is 1, and when they're the same, the result is 0.
• Example: 5 ^ 3 compares the bits of 5 (101) and 3 (011), resulting in 110, which is 6.

Steps in the Program:

• The program goes through each number in the array one by one.
• As it goes, it keeps track of the XOR of all the numbers it has seen so far.
• At each step, it checks if there's a previous subarray whose XOR, when combined with the current XOR, gives the target value b.

Using a Map:

• The program uses a "map" (or dictionary) to remember how many times each XOR result has appeared. This helps quickly check if there’s a subarray that matches the XOR we want.

Counting Matches:

• Whenever it finds a match, meaning it found a subarray that XORs to b, it increases the count.

Final Result:

• After checking all the numbers, it returns the total number of subarrays whose XOR matches b.

Think of it like a treasure hunt 🏴‍☠️. As you explore each number in the array, you keep a running total of your "XOR treasure points." You also remember all the "points" you’ve gathered along the way in a notebook (the map). Whenever you see that the points you’ve just gathered, plus what you’ve already written down, match the treasure target b, you celebrate 🎉 and increase your count of found treasures.

In the end, you tell how many treasures (subarrays) you found that have exactly the right amount of points (XOR equals b).

import java.util.*;
public class Solution {
    public static int subarraysWithSumK(int []a, int b) {
        // Write your code here
   
 int size=a.length;
    int count=0;
    Map<Integer,Integer>hm=new HashMap<>();
    hm.put(0,1);
    int xor=0;
    for(int i=0;i<size;i++)
    {
        xor=xor^a[i];
        int x=xor^b;
        if(hm.containsKey(x))
        count=count+hm.get(x);
        
        hm.put(xor,hm.getOrDefault(xor, 0)+1);
    }
    return count;
    }
}

#include<bits/stdc++.h>

int subarraysWithSumK(vector < int > a, int b) {

    // Write your code here

    int n = a.size();

    int cnt = 0;

    unordered_map<int,int> mpp;

    mpp[0] = 1;

    int xr = 0;

    for(int i=0;i<n;i++){

        xr = xr^a[i];

        int x = xr^b;

        cnt += mpp[x];

        mpp[xr]++;

    }

    return cnt;

}

#include<bits/stdc++.h>
int subarraysWithSumK(vector < int > a, int b) {
    // Write your code here
    unordered_map<int,int>mp;
    int cnt=0;
    int ans=0;
    for(int i=0;i<a.size();i++){
        ans^=a[i];
        if(ans==b){
            cnt++;
        }
        if(mp.find(b^ans)!=mp.end()){
            cnt+=mp[b^ans];
        }
        mp[ans]++;
    }
    return cnt;
}

int subarraysWithSumK(vector < int > a, int k) {

    unordered_map<int,int> m;

    int cnt=0;

    m[0]=1;

    int xr=0;

    for(int i=0;i<a.size();i++){

        xr=xr^a[i];

        if(m[xr^k]){

            cnt+=m[xr^k];

        }

        m[xr]++;

    }

    return cnt;

}

#include<bits/stdc++.h>

int subarraysWithSumK(vector<int>a,int b) {

   map<int,int>mpp;

   int xorr = 0;

   mpp[0] = 1;

   int count = 0;

   for(int i=0;i<a.size();i++) {

       xorr = xorr^a[i];

       int x = xorr^b;

       count += mpp[x];

       mpp[xorr]++;

   }

   return count;

}

#include <bits/stdc++.h>
int subarraysWithSumK(vector<int> a, int b) {

    int xr = 0, n = a.size();
    map<int, int> preXors;
    preXors[xr]++;
    int cnt = 0;

    for (int i = 0; i < n; i++) {

        xr ^= a[i];
        int remXr = xr ^ b;

        cnt += preXors[remXr];

        preXors[xr]++;

    }

    return cnt;
}

we know that if a^b = c then a^c = b or b^c = a therefore we just have to exploit this knowledge to solve :  

//solution

int subarraysWithSumK(vector < int > a, int b) {

    int xr = 0; //here xr will store previous xor values

    unordered_map<int,int> mp;

    mp[xr]++; //step 1 insert {0,1} in the map

    int cnt = 0;

    int n = a.size();

    for(int i=0; i<n; i++){

        xr = xr ^ a[i]; // will get the latest xor of prev arr elements

        int x = xr ^ b; 

        cnt += mp[x];

        mp[xr]++;

    }

    return cnt;

}

#include<bits/stdc++.h>

int subarraysWithSumK(vector < int > a, int b) {

    // Write your code here

   int c=0;

   int n=a.size();

   map<int,int> mpp;

   int temp=0;

   for(int i=0;i<n;i++)

   {

       temp^=a[i];

       if(temp==b)c++;

       int rem=temp^b;

       if(mpp.find(rem)!=mpp.end())

       {

           c+=mpp[rem];

       }

       mpp[temp]++;

    }

  return c;

}

import java.util.*;

public class Solution {

    public static int subarraysWithSumK(int []a, int b) {

        // Write your code here

        int cnt=0;

        int n = a.length;

          int  xor =0;

          Map<Integer,Integer>mpp=new HashMap<>();

          mpp.put(xor,1);

        for(int i=0;i<n;i++)

        {

            xor = xor^a[i];

            int x=xor^b;

            if(mpp.containsKey(x))

            {

                cnt+=mpp.get(x);

            }

            if(mpp.containsKey(xor))

            {

                mpp.put(xor,mpp.get(xor)+1);

            }

            else

            {

                mpp.put(xor,1);

            }

        }

        return cnt;

    }

}