0 like 0 dislike
1,884 views
Constraints :

1<=N<=1000000

1<=A[i]<=1000000000

1<=k<=1000000000
| 1,884 views

0 like 0 dislike

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;
}

a1[v] = i ;
b1[v]++;
i++;
}
if(good==0)
{
cout<<"NO";
}
else
{
cout<<possible ;
}
return 0;
}
```
by Expert (110,880 points)
selected
1 like 0 dislike
```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++;

}

}```
by
edited by anonymous