Find the shortest subarray in an array whose xor value is "k" in O(N) ?

Question

Constraints :

1<=N<=1000000

1<=A[i]<=1000000000

1<=k<=1000000000

Answer 1

Say ,  you are at index "i" . In a variable , say 'v' ,  store xor of all elements till "i" , so v = a[1]^a[2]^.....a[i] . 

Now , if there is a "j" , such that j<i , and a[j+1]^a[j+2]^.....a[i] = k , it means z^k = v , where z = a[1]^a[2]^a[3]^...a[j] . 

Now , z^k=v , hence , v^k = z , so we find the value of "z" by doing : v^k at given index "i" . (k is a constant)  . After finding "z" , we need to know the index where xor of all elements from 1 to "j" was "z" . That index is "j" . We can store xor value and corresponding index in a map . We keep updating the map everytime , at every index ,  so we always get biggest possible value of 'j' . Answer is (i-j) for subarray ending at index 'i' . 

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll ;
int main() 
{
     
     ll n ; 
     ll possible = 1e18  ; 
     cin>>n; ll k ;
     cin>>k;
     ll i = 1 ; 
     ll v = 0 ; 
     map <ll,ll> a1,b1 ;
     ll good = 0 ; 
     a1[0]=0; //xor-value<--->index 
     while(i<=n)
     {
         ll x ; cin>>x;
         v=(v)^(x);
        ll m = (v)^(k);
        if(b1[m]>=1)
        {
            good=1;
            ll answer = abs(i-a1[m]);
            possible = min(possible,answer);
        }
        
        a1[v] = i ; 
        b1[v]++;
         i++;
     }
     if(good==0)
     {
         cout<<"NO";
     }
     else
     {
         cout<<possible ; 
     }
     return 0; 
}

Answer 2

ALGORITHM

input an array of numbers

declare 2 pointers 1 and j

declare map of <int,int> ( this will store xor and freq )

keep iterating on array untill we have found our answer

once we have found our answer start shring(incrementing and taking XOR from LHS pointer)

once this ends we have our segment ready


INPUT order

n k

n elements

SAMPLE INPUT

11  10

6 9 1 2 3 7 8 4 6 0 3 10 7 8 4 8

SAMPLE OUTPUT

SEGMENT found : 9 1 2 

SEGMENT found : 8 4 6 

SEGMENT found : 10

#include<bits/stdc++.h>

using namespace std;

int32_t main()

{

    vector<int> a = {6,9,1,2,3,7,8,4,6,0,3,10,7,8,4,8};

                    //  0 1 2 3 4 5 6 7 8 9 

    int k = 10;


    int i = 0 , 

        j = 0 , 

        n = a.size(),

        ans =  INT_MAX;

    map<int,int> m;


    // lambda function to print segment captures array by reference

    auto printSection = [&a](int i, int j)

    {

        cout<<"SEGMENT found : "; 

        while(i<=j)

            cout<<a[i++]<<" ";

        cout<<endl;

    };

    int curr = 0;

    while(j<n)

    {

        curr ^= a[j];

        if(m[curr^k])   

        {

            do

            {

                --m[curr^a[i]];

                curr ^= a[i++];

    

            }while(curr != k);

            printSection(i,j);

        }

        m[curr]++;

        j++;

    }


}