Please watch the new video which covers it in more depth, and also prints it: th-cam.com/video/eZr-6p0B7ME/w-d-xo.html Understooooooooooooooood? . Instagram(connect if you want to know how a SDE's normal life is): instagram.com/striver_79/ . . If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
please tell the expected time complexity and space complexity before solving so we can at least try ourselves first. i havent solved it yet can you please tell?
@@udaygohil4875 Actually a better way to do this problem is by just using a freq array instead of map, we know that for N elements the prefix XOR of all the elements can never be > 2 * N so we can use if(pref ^ k < 2 *N) res += freq[pref ^ val], gives the same result
It's one of the best algorithm I have seen so far, very hard to get intuition at first-sight but you have explained it so nicely. For that hat's off to you. Also please come up with such problems regularly🥰
Thank you this is great.....similar problem is present in my last google internship test and I couldn't solve it .....I try to find how to solve this problem but I didn't find any good solution but this video clears everything.
Superb explanation. If anyone is still struggling to understand the intuition, do the dry run yourself in pen and paper. Whenever you increment the count, find out the subarrays the count refers. It will be clear to you.
the way Striver provides the intuition behind the algorithm is something that sets him apart from most of the people who do the same. Guess this comes naturally to someone who's been been doing CP for years :). Great work!
understoooooood finallyyyy, it was really hard to explain and understand, its like ab hm current point tk XOR check krrhe anddd jo current tk xor value hai uska if m ke sth XOR lete and jo value hota if wo pehle kahi encounter hua tha , toh wo encountered prefix tk and current ke bich ka diff wla xor hi m hai Recommended isey 2-3 baar suno, full focus ke sth , jb tk smjh na aaye tb tk suno , bina fast forward krey
If someone is still unable to get how Y = XR ^ k, then consider XORing both sides of the original equation with k. i.e. Y ^ k ^ k = XR ^ k. Since, k ^ k = 0, we will get the final equation as Y = XR ^ k. :)
just simply xor with 'k' initial is ---> Y=XR^K XOR BOTH SIDES WITH 'k'. K^Y=XR^K^K now see K^K is 0; now it boils down to K^Y=XR^0; now A^0 is 'A', the exclusive OR peoperty so XR^0 = XR; now it becomes K^Y=XR; now you can mutiply this initial equation --> Y=XR^K with XR also , on both the sides obviously and then see it becomes K=XR^Y; //so you can solve it either way. if still not understood i will highly recommend to watch a video on "Exclusive OR" operator and understand its bit operations.
There are some prerequisites to understand this problem. It would be easier if you have read some text - XOR is commutative (X ^ Y = Y ^X) - X ^ 0 = X - X ^ X = 0 - Proof If A ^ B = C (XOR'ing both sides by B, we get A ^ B ^ B = C ^ B. As we know B ^ B = 0, hence, proved :: A = C ^ B
yes bro its very easy apne jis tarah smjaya us tarah se sayad koi youtuber smja nhi skta ha but sayad apke video dekhne se sayad ye problem samaj nhi ayega apke sath sath note pen me krne se hi smj a skta he without pen papper koi coder code nhi kar skta
Took ne 1 hour 2 mins to understand this 16 minutes video ...have been searching for this question for 10 days...today i understand within 2 hours ... Thanks bhai Th ak
Watch it 3 times to understand. Watch 2 time to understand logic. Then code it out with same steps as in video, even if you don't understand it completely. Then watch the video again. AND DONE.
For those who still don't get it. Pause at 10:14 and read this: We maintain a XOR Map because if [4, 2, 2, 6] has XOR = 2 it's not equal to k, which is 6. So check what is 2 ^ 6? It's 4. Which means there's a subarray in the current subarray [4,2,2,6], which has XOR=4. Which means that 2 parts of subarray [4,2,2,6] have XOR=4 and XOR=6, which together combined make XOR=2. We just want the part which has XOR=6. So we check how many subarrays with XOR=4 are there in the subarray [4,2,2,6], because it is also the number of how many subarrays with XOR=6 are there in subarray [4,2,2,6] (Since the 2 subarrays with XOR=4 and XOR=6 must be in equal quantities, otherwise they can't make XOR=2 together) So, make a prefix xor sum array, every number will represent the XOR sum from 0 to its current index. Then loop through every number. If XOR = k, count++; (because the subarray from 0 till now has XOR=k) otherwise, check if mp[xorsum^k] exists, if yes, then count += mp[xorsum^k] (because mp[xorsum^k] is the number of subarrays inside the current subarray with XOR = k) after this mp[xorsum] += 1; (Push the XOR at the current index from prefix array, which in this case is 2 to the map, because we'd like to keep track of all XOR prefixes) So all we're doing is checking in the current subarray for how many subarrays with XOR=k do we have and those number of subarrays with XOR=k are the same as the number of subarrays with XOR=currentPrefixXOR ^ k
The intuition is slightly wrong here, we don't compute K^X and check in the hashmap but rather compute (Y+K) ^ X = Y as we have the xor sum from index 0 till i. so if we find a match in hashmap, Y = (Y+K) ^ X (and not Y = K ^ X) Y^Y + Y^K = X 0 + Y^K = X (since a^a=0) Y^K = X which is the formula which we have but the derivation is wrong in the video. But in any case, great video!
It's a prefix xor, it has the value of xor from idx(o to current). Ex: pointer is @ idx 2 this means xor variable will contain the value(xor = 0^1st value (assume x, 0 because initially it is 0), then xor= x^2nd value (assume y), then xor=y^3rd value(assume z). And so on for the coming indexes as well. Hope this clears the doubt.
This solution Doesnt Work On Gfg ?? I alwys Appreciate Efforts Bhaiya, but Please Explain those Solutions Which'll be Working on any Of Coding Platforms
Hashmap insertion and retrieval takes O(1) in best case but in worst case it takes O(logN). So overall worst case time complexity becomes O(NlogN). N for loop and logN for Hashmap insertion or retrieval.
First of all,how are you calculating this xor mentally?Is there an easy way without converting to binary and getting the result like directly by seeing these decimal numbers?
It comes from using an ordered map in c++ or a treemap in Java. Searching and inserting in ordered map or treemap is logn, and we do the entire procedure n times, therefore O(nlogn)
I had the same doubt initially. So, basically the TC would be O(n) in the average case but for the worst case scenario, it would be O(n logn) due to the fact that hashmaps are implemented using self balancing BST and the worst case to search an element is O(log n), and finally there are n elements so overall O(n logn).
@@JAYPRAKASH-uy8rg But then again insertion must be O(log n) in worst case too if we consider a BST regaining balance after insertion. So it should be O(NlogN + NlogN)
Please watch the new video which covers it in more depth, and also prints it: th-cam.com/video/eZr-6p0B7ME/w-d-xo.html
Understooooooooooooooood?
.
Instagram(connect if you want to know how a SDE's normal life is): instagram.com/striver_79/
.
.
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
upload frequency ⬆⬆⬆ Thank you!
This is one of the best videos!
please tell the expected time complexity and space complexity before solving so we can at least try ourselves first. i havent solved it yet can you please tell?
It cleared my concepts. Thanks a lot.
@@vishalm784 everything works, do the dry run, u will get to know!
This algo was not easy to explain but you did it in a very lucid ways. Awesome work.
Would you explain the time complexity please?
@@udaygohil4875 O(n) if you assume hashing(unordered_map for C++11 and onwards) works in O(1) time, otherwise it's O(nlogn)
@@udaygohil4875 Actually a better way to do this problem is by just using a freq array instead of map, we know that for N elements the prefix XOR of all the elements can never be > 2 * N so we can use if(pref ^ k < 2 *N) res += freq[pref ^ val], gives the same result
It's one of the best algorithm I have seen so far, very hard to get intuition at first-sight but you have explained it so nicely. For that hat's off to you. Also please come up with such problems regularly🥰
Thank you this is great.....similar problem is present in my last google internship test and I couldn't solve it .....I try to find how to solve this problem but I didn't find any good solution but this video clears everything.
Superb explanation. If anyone is still struggling to understand the intuition, do the dry run yourself in pen and paper. Whenever you increment the count, find out the subarrays the count refers. It will be clear to you.
The solution is easy but the intuition🙏 Great to have guys like you explaining things so beautifully ❤️
When I say it I mean it brother, you are a definition of how a teacher should go with explanation of stuffs.
the way Striver provides the intuition behind the algorithm is something that sets him apart from most of the people who do the same. Guess this comes naturally to someone who's been been doing CP for years :). Great work!
hey by the looks of it, it seems as if u understood it ! Can u just explain me why is the time complexity nlogn and not n???
understoooooood finallyyyy, it was really hard to explain and understand, its like ab hm current point tk XOR check krrhe anddd jo current tk xor value hai uska if m ke sth XOR lete and jo value hota if wo pehle kahi encounter hua tha , toh wo encountered prefix tk and current ke bich ka diff wla xor hi m hai
Recommended isey 2-3 baar suno, full focus ke sth , jb tk smjh na aaye tb tk suno , bina fast forward krey
Perfect way of explaining the intution..
I am just 2:25 in the video and I got the ans by trying myself it is all because of your previous video, thanks
EASY implementation
int Solution::solve(vector &v, int k) {
map mp; mp[0]=1;
int sum=0,ans=0;
for( int i=0; i
If someone is still unable to get how Y = XR ^ k, then consider XORing both sides of the original equation with k. i.e. Y ^ k ^ k = XR ^ k. Since, k ^ k = 0, we will get the final equation as Y = XR ^ k. :)
hey.....i have a similar question...can you please help me solve it
Thanks :)
thanks bro, now I understand😊😊
just simply xor with 'k'
initial is ---> Y=XR^K
XOR BOTH SIDES WITH 'k'.
K^Y=XR^K^K
now see K^K is 0;
now it boils down to
K^Y=XR^0;
now A^0 is 'A', the exclusive OR peoperty
so XR^0 = XR;
now it becomes
K^Y=XR;
now you can mutiply this initial equation --> Y=XR^K
with XR also , on both the sides obviously and then see it becomes K=XR^Y;
//so you can solve it either way.
if still not understood i will highly recommend to watch a video on "Exclusive OR" operator and understand its bit operations.
Bhai.. common sense
Y ^ K = XOR
4 ^ 6 is 2
Now
Y = XOR ^ k
Y = 2 ^ 6
Y is 4
In both ways we get same value of Y
Yesterday's codeforces question C is based on this concept
wonderful explanation!!
There are some prerequisites to understand this problem. It would be easier if you have read some text
- XOR is commutative (X ^ Y = Y ^X)
- X ^ 0 = X
- X ^ X = 0
- Proof If A ^ B = C (XOR'ing both sides by B, we get A ^ B ^ B = C ^ B. As we know B ^ B = 0, hence, proved :: A = C ^ B
yes bro its very easy apne jis tarah smjaya us tarah se sayad koi youtuber smja nhi skta ha but sayad apke video dekhne se sayad ye problem samaj nhi ayega apke sath sath note pen me krne se hi smj a skta he without pen papper koi coder code nhi kar skta
Took ne 1 hour 2 mins to understand this 16 minutes video
...have been searching for this question for 10 days...today i understand within 2 hours ...
Thanks bhai
Th ak
Rewind karte karte or video phir se ek or baar dek liya. Ab samaj aagaya. Worth it!! Keep up the good work🤗
Great Great Concept explained in so simple words. Just loved every minute of it!
What a video brother !! Thanks for helping people like me so much ❤️😍
Was able to get this approach by myself for this problem after solving similar questions like largest 0 sum subarray & number of K sum subarrays.
Literally hats off
You are inlighting the world through your knowledge
sir instead of if (xorr == B) cnt++ can we also use freq[0] = 1 initially
Yeah
This question is similar to subarray with sum K. Thanks for the great explanation.
This series is so great , that even if i was paying for this i would have been Happy.
Great Work!
I am yet to join college but i subscribed this channel to extend my support
WHAT A WONDERFUL QUESTION !
Awesome Explanation. This is a complex algorithm to teach someone but you have done an excellent job.
similar leetCode question is Subarray Sum Equals K .
📢📢😁For better understanding --> Consider this question as --> count number of subarrays with sum as k. And do a dry run urself. U will get it clearly.
love the voice modulation u do for explaining :)
Finally got it. Thank you for such great explaination.
Explanation was nothing less than a magic! Thankyou sir 🙏
It took me 30-45 min to actually undersatnd the algo, but at the end i got it well
Hats off to your patience....
how u r finding XOR of two nums in seconds while dry run?
Thank you so much for these videos .
It really helps me a lot in understanding these.
Thanks for detailed explanation. very good way and efforts for explaining the problem.
Awesome explainations!!
Great explanation man ...you know where students can face trouble
this for some reason does not work on GFG problem, Subsets with XOR value
Watch it 3 times to understand.
Watch 2 time to understand logic.
Then code it out with same steps as in video, even if you don't understand it completely.
Then watch the video again.
AND DONE.
For those who still don't get it.
Pause at 10:14 and read this:
We maintain a XOR Map because if
[4, 2, 2, 6] has XOR = 2 it's not equal to k, which is 6.
So check what is 2 ^ 6? It's 4.
Which means there's a subarray in the current subarray [4,2,2,6], which has XOR=4. Which means that 2 parts of subarray [4,2,2,6] have XOR=4 and XOR=6, which together combined make XOR=2.
We just want the part which has XOR=6.
So we check how many subarrays with XOR=4 are there in the subarray [4,2,2,6], because it is also the number of how many subarrays with XOR=6 are there in subarray [4,2,2,6] (Since the 2 subarrays with XOR=4 and XOR=6 must be in equal quantities, otherwise they can't make XOR=2 together)
So, make a prefix xor sum array, every number will represent the XOR sum from 0 to its current index.
Then loop through every number.
If XOR = k, count++; (because the subarray from 0 till now has XOR=k)
otherwise, check if mp[xorsum^k] exists, if yes, then count += mp[xorsum^k] (because mp[xorsum^k] is the number of subarrays inside the current subarray with XOR = k)
after this mp[xorsum] += 1; (Push the XOR at the current index from prefix array, which in this case is 2 to the map, because we'd like to keep track of all XOR prefixes)
So all we're doing is checking in the current subarray for how many subarrays with XOR=k do we have and those number of subarrays with XOR=k are the same as the number of subarrays with XOR=currentPrefixXOR ^ k
There's one subarray this algo doesn't consider: [2,2,6]
Great explanation of a tough problem 🤩
Nice explanation, thank you for taking us forward!
Striverr bhaiyyaaa jodddddddddddd tysmmmmmm understoooood......
4:55
This XOR this is going to be this
I thing I don't need to explan this
haha best part of the video very funny and great explanation
thanks for the video! what software do you use to draw?
Wacom tablet
Beautiful explanation brother!! Thank you.
The intuition is slightly wrong here, we don't compute K^X and check in the hashmap but rather compute (Y+K) ^ X = Y as we have the xor sum from index 0 till i.
so if we find a match in hashmap,
Y = (Y+K) ^ X (and not Y = K ^ X)
Y^Y + Y^K = X
0 + Y^K = X (since a^a=0)
Y^K = X
which is the formula which we have but the derivation is wrong in the video.
But in any case, great video!
best explaination i ever heard
Great initiative bhai and concepts are crystal clear
Bhaiya how much knowledge about data structures is needed for learning stl. Pls reply.
Wah bhaiya full codingbaazi..
Well explained bhaiya
Striver thankyou for helping us
Nice explanation your videos are really good...keep making such videos.
If condition is ( xorr >= k ) , Then what should be the changes in the code ?
My Journey of DSA is going Damn smooth because of Striver
Why is the 5th Chapter of video named as 'Dry Iron' ☠ @takeuforward
great explanation. thanks for ur efforts.
What's the use of xor variable you considered while explaining??
It's a prefix xor, it has the value of xor from idx(o to current). Ex: pointer is @ idx 2 this means xor variable will contain the value(xor = 0^1st value (assume x, 0 because initially it is 0), then xor= x^2nd value (assume y), then xor=y^3rd value(assume z). And so on for the coming indexes as well. Hope this clears the doubt.
Where to practice this question?
Good explanation
Brother, I never shall forget your favor 🥺
why we are using two if can we use if and else if ?
God-level explanation 🔥
N = 5
K = 4
arr: 1 2 3 4 5
not giving correct output for above input
This solution Doesnt Work On Gfg ?? I alwys Appreciate Efforts Bhaiya, but Please Explain those Solutions Which'll be Working on any Of Coding Platforms
hats off man!
nice clear explanation
Brilliant explanation ....)
public class Solution {
public int solve(ArrayList A, int B) {
int count = 0;
Map hm = new HashMap();
int runningXor = 0;
hm.put(runningXor, 1);
/*
4, 2, 2, 6, 4
rXor = Y ^ B;
rXor ^ B = Y;
*/
int key = 0;
for(int i = 0; i < A.size(); i++) {
runningXor ^= A.get(i);
key = runningXor ^ B;
if(hm.containsKey(key)) {
count += hm.get(key);
}
hm.put(runningXor, hm.getOrDefault(runningXor, 0) + 1);
}
return count;
}
}
please xplain maximum subset xor question
YOU ARE MY INSPIRATION!!!!!
Great explanation.. thanks
Just wow
Brute force of Subarray Problems : Generate all Subarrays by using Kadanes Algo
TC : O( n^2)
thanks man!
this code and approach not working for gfg subsets with xor value question, plz help
Thankyou sir
Understooooooooooooooood!!!!!!!!!!!!
Thanks bhaiya🔥
Hi, I understood the algorithm but didnt got how TC=O(nlogn) and not O(n) ??
Hashmap insertion and retrieval takes O(1) in best case but in worst case it takes O(logN). So overall worst case time complexity becomes O(NlogN). N for loop and logN for Hashmap insertion or retrieval.
Thanks it was helpful
First of all,how are you calculating this xor mentally?Is there an easy way without converting to binary and getting the result like directly by seeing these decimal numbers?
you just need to imagine the binary form and observe which bits are in common and subtract their decimal result as they got cancelled because 1^1 is 0
13:25 😂😂 aree argue nhi baas pucha tha. Tum toh bura maan gaye. I apologise if I made you think that. Thanks for helping out anyways. 😊
Sir, cpp code would be better
Best explanation 😍😍
Suppose we want to find the number of subarrays for even K, how will we use this algo? Can someone help?
It took time, But worth it!
For the people who are not able to digest it, let me tell you that this is actually a property:
If A xor B = C , then B xor C = A.
thankYou striver
Thanks bro👍👍👍
samaj nahi aaya par sunke accha laga
Wow!
What if the last element is 0 ?
Why N * logN TC? An unordered map takes O(1) amortized. Even if in the worst case it takes O(N) then also, It should be N^2? Can u explain please/
In worst case it takes O(n) which is mentioned on Gfg but they tell it happens occasionally so you can also say O(logn):)
Nice explanation but could be explained in a better way.
Why is the time complexity O(nlogn)? Where does the log n come from?
It comes from using an ordered map in c++ or a treemap in Java. Searching and inserting in ordered map or treemap is logn, and we do the entire procedure n times, therefore O(nlogn)
I had the same doubt initially.
So, basically the TC would be O(n) in the average case but for the worst case scenario, it would be O(n logn) due to the fact that hashmaps are implemented using self balancing BST and the worst case to search an element is O(log n), and finally there are n elements so overall O(n logn).
@@JAYPRAKASH-uy8rg Okay thank you for explaining :)
@@JAYPRAKASH-uy8rg But then again insertion must be O(log n) in worst case too if we consider a BST regaining balance after insertion. So it should be O(NlogN + NlogN)
@@aishwaryamajumdar6927 it should be O(logn) for searching
why we are using two if condition why cannot one if ans else if
Sir this code of your is not giving me the correct ans in my pc ,i dont know why.pls help