CODEWITHSUNDEEP
algorithmbit-manipulationxortriebitwise-xor
sanketd617
sanketd617

Reputation: 809

Finding subarray whose xor is 0

I'm stuck at one problem i.e. to find a subarray whose xor is 0. I read somewhere that this can be done using TRIE data structure but I want the starting and ending indices of the array.

For example, consider an array

a = [3, 6, 13, 8 15]

The subarray from 0 to 3 i.e. [3, 6, 13, 8] has xor equal to 0. (3 xor 6 xor 13 xor 8 = 0) I'm in search for an algorithm than can find those indices ([0, 3] in this case).

Detailed answer would be very helpful.

Update I tried the brute Force approach find checking xor for all pairs of [i, j]. This gives TLE since the no. of elements in the array could be upto 10^5

The I tried a solution mentioned here but this doesn't give indices.

I'm looking for an algorithm with O(nLogn) or possibly O(n) complexity.

Upvotes: 0

Views: 1980

Answers (1)

Faruk Hossain
Faruk Hossain

Reputation: 1203

This solution take O(n) complexity also. Take the benefit of unordered_map.

vector<int> a = {3,6,13,8,15};
unordered_map<int, int> hashMap;
int number_of_elements = a.size();
hashMap[0] = -1;
int xor_sum = 0;
for(int i = 0; i < number_of_elements; i++) {
    xor_sum ^= a[i];
    if(hashMap.find(xorSum) != hashMap.end()) {
        cout << hashMap[xorSum] + 1 << " " << i << endl;
        break;
    }
    hashMap[xor_sum] = i;
}

Upvotes: 1

Related Questions