XOR Queries of a Subarray | Simple Explanation | Leetcode 1310 | codestorywithMIK

This is the 18th Video of our Playlist "Bit Manipulation : Popular Interview Problems" by codestorywithMIK

In this video we will try to solve an easy problem : XOR Queries of a Subarray | Simple Exlpanation | Leetcode 1310 | codestorywithMIK

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : XOR Queries of a Subarray | Simple Explanation | Leetcode 1310 | codestorywithMIK
Company Tags : will update soon

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Summary :
The problem is solved using cumulative XOR (prefix XOR) to efficiently handle multiple range XOR queries. The approach involves two main steps:

Precompute Cumulative XOR:

First, we create an array cumXor where each element cumXor[i] stores the XOR of all elements in the input array arr from the beginning up to index i. This allows us to compute the XOR of any subarray in constant time.
The cumulative XOR is computed in a single pass over the array (O(n)).
Answer Queries Efficiently:

For each query, which provides a range [L, R], the XOR of the subarray from L to R is computed as cumXor[R] ^ cumXor[L-1]. If L is 0, the XOR result is simply cumXor[R].
This allows each query to be processed in constant time (O(1)), making the overall time complexity O(n + q), where n is the size of the array and q is the number of queries.
This approach is efficient because it reduces the time complexity from O(n*q) (brute force) to O(n + q) by using precomputed values.

✨ Timelines✨
00:00 - Introduction

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[study-ydes]

Keep uploading these type of amazing sirrr <3

[MeetPatel-ywti]

sir i learnt a lot of dsa concept in your channel, ...thanks a lot, ...keep it up

[Ankitkumar-fzkc]

Did it my own. But still here so that I can learn something new.

[YashMalav-khov]

sir is the segment tree playlist complete or more videos will be coming into it also please whenever there is a easy potd and you upload only code that day please make video on segment tree

[alonecoder-flri]

mik bhaiya releases our pressure during thought process just like the the pressure cooker does in background.💯

[doremon]

background mein cooker ki siti bajj rahi hai kya?

[arnabsarkar]

Did it on my own, but cant skip your videos...

[AbhishekKumar-hupz]

bhaiya you should make a dsa playlist of every concept as soon as possible rather than doing only leetcode problem daily, so that your channel become one stop solution for dsa.
honestly i am saying i have never seen a better teacher than u for dsa.. so please make playlist of every concept.

[aryansrivastava]

the brute force does gets accepted O(m*n), the constraints are not that tight

[vickyroy]

Hi Mik, I ll tell you a good news if i get offer!!

[RishabhChatterjee-fggz]

Bhaiya mene ye question khud se Kiya par wo bhi aap hi se para hua ek concept se banaya hu, prefix xor like prefix sum

[namansaini]

Can this question be done using segment trees ?

[rohan]

*Java code:*

// TC: O(n) calculate prefix/cumulative xor + O(q) //iterate through queries
// SC: O(n) //store prefix/cumulative xor

// TC: O(n)
public static int[] cumulativeXor(int[] arr) {
int n = arr.length;
int[] cumulative = new int[n];
// cumulative xor of [0, 0] will be arr[0] itself
cumulative[0] = arr[0];

for (int i = 1; i < n; i++) {
cumulative[i] = cumulative[i - 1] ^ arr[i];
}
return cumulative;
}

//main motive xor of two same number is always 0 or negligible
public static int[] xorQueries(int[] arr, int[][] queries) {
int n = arr.length;
int q = queries.length;
int[] res = new int[q];
int indx = 0;

int[] cumulative = cumulativeXor(arr);

for (int[] temp : queries) {
int start = temp[0];
int end = temp[1];

if (start == end) {
res[indx++] = arr[start];
} else if (start == 0) {
res[indx++] = cumulative[end];
}

else {
res[indx++] = cumulative[end] ^ cumulative[start - 1];
}
}
return res;
}

[manjushborse]

java
class Solution {
public int[] xorQueries(int[] arr, int[][] queries) {
int n=arr.length;
int[] pf=new int[n];
int m=queries.length;
int[] ans=new int[m];
pf[0]=arr[0];
for(int i=1;i<n;i++)
{
pf[i]=pf[i-1]^arr[i];
}
int i=0;

for(int[] q:queries)
{
int l=q[0];
int r=q[1];

if(l==0)
{
ans[i]=pf[r];
}
else
{
ans[i]=pf[r]^pf[l-1];
}
i++;
}
return ans;
}
}

[aryansrivastava]

I solved it using prefix count of bits, by maintaining how many set bits are there up to to each number
class Solution {
public:
vector<int> xorQueries(vector<int>& a, vector<vector<int>>& q) {
vector<vector<int>>prefixBits(a.size(), vector<int>(32, 0));
vector<int>ans;
for(int i = 0; i < a.size(); i++){
int num = a[i];
for(int j = 0; j < 32; j++){
prefixBits[i][j] += ((num >> j) & 1);
}
}
for(int i = 1; i < a.size(); i++){
for(int j = 0; j < 32; j++){
prefixBits[i][j] += prefixBits[i-1][j];
}
}

for(int i = 0; i < q.size(); i++){
int l = q[i][0], r = q[i][1], mask = 0;
for(int j = 0; j < 32; j++){
int cnt1;
if(l - 1 >= 0){
cnt1 = prefixBits[r][j] - prefixBits[l-1][j];
}
else cnt1 = prefixBits[r][j];

if(cnt1 % 2 == 1){
mask = (mask | (1 << j));
}

}
ans.push_back(mask);
}

return ans;
}
};

[faizanalam]

Mai to solve krke yaha aaya hu ye question to easy marked hona chahhiye

[Summerslow]

Bhaiya i think we can also Use segment and Fenwick tree please if thats right post that solution too

[dynamictip]

If you don't want to handle edge case separately then:
public int[] xorQueries(int[] arr, int[][] queries) {
HashMap<Integer, Integer> hm=new HashMap<>();
int xor=0;
for(int i=0;i<arr.length;i++)
{
xor^=arr[i];
hm.put(i, xor);
}
int ans[]=new int[queries.length];
for(int i=0;i<queries.length;i++)
{
int b=queries[i][1];
int a=queries[i][0];
int
ans[i]=res;

}
return ans;

}

Thanks for your video explanation!

[GateDA-omkarpunjaji]

class Solution {
public:
void buildTree(vector<int> & arr, vector<int> &segmentTree, int idx, int l, int r){
if(l == r) {
segmentTree[idx] = arr[l];
return;
}
int mid = l + (r - l) / 2;

buildTree(arr, segmentTree, idx * 2 + 1, l, mid);
buildTree(arr, segmentTree, idx * 2 + 2, mid + 1, r);

segmentTree[idx] = segmentTree[idx * 2 + 1] ^ segmentTree[idx * 2 + 2];
}

int rangeQ(vector<int>& arr, vector<int>& segmentTree, int idx, int l, int r, int left, int right) {

if(right < l || left > r) return 0;

if(left <= l && r <= right) return segmentTree[idx];

int mid = l + (r - l) / 2;
int lans = rangeQ(arr, segmentTree, idx * 2 + 1, l, mid, left, right);
int rans = rangeQ(arr, segmentTree, idx * 2 + 2, mid + 1, r, left, right);

return lans ^ rans;
}

vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
int n = arr.size();
vector<int> segmentTree(4 * n, 0);

buildTree(arr, segmentTree, 0, 0, n - 1);

vector<int> res;
for(auto &q : queries) {
int left = q[0];
int right = q[1];

int temp = rangeQ(arr, segmentTree, 0, 0, n - 1, left, right);
res.push_back(temp);
}

return res;
}
};

[factinsaan]

class Solution {
public:
vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& q) {
int n = arr.size();
vector<int> ans;
vector<vector<int>> v(n, vector<int>(32, 0));
for (int i = 0; i < n; i++) {
if (i > 0)
v[i] = v[i - 1];
for (int j = 31; j >= 0; j--) {
if (arr[i] & (1 << j))
v[i][j]++;
}
}
for (auto it : q) {
vector<int> temp(32, 0);
if (it[0] == 0) {
temp = v[it[1]];
} else {
for (int i = 0; i < 32; i++) {

temp[i] %= 2;
}
}
for (int i = 0; i < 32; i++)
temp[i]%=2;
int sum = 0;
for (int i = 0; i < 32; i++)
sum += (temp[i] * (1 << i));
ans.push_back(sum);
}
return ans;
}
};