Number of Subarrays with xor K | Brute - Better - Optimal
HTML-код
- Опубликовано: 6 июл 2024
- Problem Link: bit.ly/3jLfElm
Notes/C++/Java/Python codes: takeuforward.org/data-structu...
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
0:00 Introduction of Course
01:08 Problem Statement
03:05 Brute force approach
03:46 Pseudocode
05:43 Complexity
06:11 Better approach
07:23 Pseudocode
07:38 Complexity
08:04 Optimal approach
08:11 Intuition
15:18 Pseudocode / Dry-run
21:28 Code
23:21 Complexity
Please watch our new video on the same topic: ruclips.net/video/eZr-6p0B7ME/видео.html
ye kya recursion chala rhe ho
😂😂@@abhijeetkumar7573
We deserve one like, isn't it 😍
One is a small no for the efforts❤️
Yes
Deserves much more❤❤
for anyone not able to solve this one try to relate it to the count subarrays with sum k using prefix sum intuition that code is exactly similiar just dry run once and you will be able to solve it , may be most people are not able to solve it in mind or paper because it is difficult to solve xor in mind than the addition or subtraction , I hope this helps 👍
i was just typing the same. Thanks buddy
After understanding the "count subarray with sum K" problem and trying this one on my own, I was able to solve it without looking at the video solution beforehand. Thank you so much sir :) Understood!!
I haven't watched this lecture but I would like to thank you for all of your previous efforts. Currently solving your DSA sheet and whenever I'm stuck at a problem your explanation make it a piece of cake. Thanku bhaiya 💯
The Best explanation I get. Yesterday only encounter a question in contest Subarray with AND k. So instantly came here to learn.
Understood! Super awesome explanation as always, thank you very very much for your effort!!
UNDERSTOOD........Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
01:08 Problem Statement
03:05 Brute force approach
03:46 Pseudocode
05:43 Complexity
06:11 Better approach
07:23 Pseudocode
07:38 Complexity
08:04 Optimal approach
08:11 Intuition
15:18 Pseudocode / Dry-run
21:28 Code
23:21 Complexity
Itna time question solve krne me diya hota to zyada fayda hota. Khair.
Arre, Mene pura video dekhne ke bad mein hi pura samaj kar Timestamp add Kiya hua hain... Bina pura samje kese mein add kar sakta hu
@@mehulthuletiya497 koi na 💀
understood. for those who are confused why we initialize over the map as {0, 1}, xor equals zero should be present otherwise we will generate one answer less than expected. Do dry run and you will get it.
We can avoid initializing map if we put one more condition "if(xr == k)cnt++;"
Amazing concept explanation!
Very nice explanation sir, Thank you!
Understood boss..
We miss you Striver
Understood, thank you.
Basically we have to find and check whether x^xr = k with current element. calculate xr with current ele and for x we have derived formula. now if you have xor value with x in hashmap, increment count then add current xor to hashmap.
Understood✅🔥🔥
شرح جميل جدا... احبك سيدي ❤❤❤
Great and detailed lecture as always. But please do include java code too
nice explanation striver sir❤
understood ,tnx for the great explanation ❤❤💕💕👌👌👌👌
Great Lecture........
UNDERSTOOD
Understood 💯💯💯
Jaldi videos banado bhai, padhne ka man ho raha hai boht zyada
Understood!
Understood ❤❤
Understood 🎉
understood!!
Hey guys just a heads up, the link in the sheet leading to GFG platform considers even non contiguous array subsets as answers, therefore leading to failed testcases.
Exactly.
thats actually a problem of DP dont so with this approach, use recursion
thanks for mentioning this. You saved me alot of time
@@Yonatan2479 Dont mention it ✌️
hey thanks !
Thanks bro. understood
understood it clearly
Nice video love u bro
understood :)
23:57 here your map stores x values with 0 ( cnt+= mpp[x] ) if x not exists, so if we have uniques x every time then your space complexity will we O(2n)
1st n for every unique xr and 2nd n will be for unique x :) tell me if I am wrong or right ! btw you are the best teacher >>
Bhaiya, I think at 22:44 instead of checking the presence of x in the map like that, it would be better if we manually check that by using conditional statement. Both are giving the same result but in your case unnecessary values are getting stored in the map because of this like cnt+=mpp[x]. If x is not present it does give zero but x is also getting added to map which is not required.
int subarraysWithXorK(vector < int > a, int b) {
int cnt=0;
int curXor=0;
unordered_map prevXors;
prevXors[curXor]++;
for(int i=0;i
this is actually the most optimal solution, thanks bro
understood
Understood
Understood! 🫡
underatood
understood.
is there anyone who is unable to think of optimized solution on their own?i hope it's not me alone!!!
of course its difficult, no one can invent solutions like this, then also code properly, without any errors satisfying those test cases, and that too in a 40 minutes exam/interview. All we can do is to study as many questions as possible, and hope if by practice and luck, those questions come, maybe with a slight variation. Solving an entire new question altogehter is too diffuclt.
@@utsavseth6573 Exactly
why we have not taken the condition where if (xr == k) we increment the count because that also will be a subarray starting from 0th index , right , having the xor as k
Great
❤
dont use the link from SDE sheet to get to CN site , just search the question or u will get to the wrong question
I can understand your optimal solution but at first go when I tried my self I'm not able to come up with this approach. how to improve this thing.
Trial and error... striver's problem solving videos are not about problem solving... he teaches how to approach a problem... not how to solve one particular problem... that is ... each and every problem solving video is this DSA playlist of his are different..
Each having different approaches... learn the approach and understand when and why we need them... a strong grasp in the sorting algorithms and its logical implementation around when, why and how we implement it would help you... most of the problem solving questions are based on these approaches or the combination of these approaches. Good luck brother ❤
Code not working for gfg platform
It requires DP approach
striver please complete the string parts.
it is same as longest subarray whose sume is k !!
bhaiya unique no occurences wala que kara dena
bahut pareshan ho chuka hu is que me
Arre, Map + Set ka use karlo ho jayega Jo basic concept aate hoge to.
Intuition:
Map (Frequency + size) + Set (Unique element + size)
If ( map size == set size)
Means have a unique no of occurrence.
how to proceed with subsets in this problem!
DP
For those jinka GFG pe ye code run nahi horha, the problem there is asking for subsets, which need not be continuous. So to solve that problem, we have to apply concept of dynamic programming. Jinko dekhna hai how this works they can look for video number 17 in striver's DP playlist.
And jinko sirf code submit krna hai, here is the code:
class Solution{
public:
int recur(int index, int val, int k, vector &arr, vector &dp){
if(index==arr.size()){
if(val==k) return 1;
return 0;
}
if(dp[index][val]!=-1) return dp[index][val];
int pick=recur(index+1,val^arr[index],k,arr,dp);
int notPick=recur(index+1,val,k,arr,dp);
return dp[index][val]=pick+notPick;
}
int subsetXOR(vector arr, int N, int K) {
vector dp(N+1,vector(5000,-1));
return recur(0,0,K,arr,dp);
}
};
the intuition was like maths theorem like to prove this that .....
What to do it xor -> and😢
Bhai sliding window ka bhi playlist bna do
He's making videos following his A2Z sheet so
i can do dsa
Bhaiya pls videos thodi jaldi lao na
haan aur ek aaj aaega
ye week arrays khatam kr dengey, fir next week se binary search suru!
@@takeUforward Yes bhaiya waiting for it🙌❤️ You are doing great work💫
@@takeUforward bhai sliding window ka bhi playlist
@@takeUforward damn Mann salute 🫡 to your efforts, you are an inspiration
7:40
Good explanation but same problem with slightly modified. You have already have so many videos. Please make unique problem videos
The reason you find it easy is because I teach you problem solving and not mugging up :) This is the reason we follow patterns, how will I produce unique patterns now ;)
@@takeUforward exactly
ok
Bhai teri avaz ben 10 alien force/ultimate alien wali hai
us
Mujhe problem samajh aa jata par code nhi kar pata. Kya karu mai
mere sath bhi same hota hai bhai , maine bhi abhi start krra hai , mayB hamne itna code nai krra ki problem smjhne baad code kr paye . solution mile toh batao
Easy tag ke 50-60 problems bana lo gfg pe, aise jismein solution naa dekhna pade 100% tum karhi lo waise probs , toh aise probs jo tumne pehle kabhi dekha naa ho aur tum khud se bana le rhe ho agr, toh yeh confidence boost karega, then with time confidence + implementation practice mil ke tough probs bhi banne lageinge!
public class Solution {
public int solve(ArrayList A, int B) {
Map map=new HashMap();
map.put(0,1);
int xor=0;
int count=0;
for(int n:A){
xor=xor^n;
int x=xor^B;
if(map.containsKey(x)){
count+=map.get(x);
}
map.put(xor,map.getOrDefault(xor,0)+1);
}
return count;
}
}
such a poor explanation when compared to other problem explanations
he don't know how to teach
You don't know how to study
#include
int subarraysWithSumK(vector < int > a, int b) {
// Write your code here
int num=0;
mapm1;
m1[0]++;
int xr=0;
for(int i=0;i
UnderStood
Understood!
Understood
understood
Understood !
Understood
Understood
Understood
Understood
Understood
Understood
Understood
Understood
Understood
Understood
Understood
Understood
Understood
Understood
understood
understood
understood
understood
understood
understood
understood
understood
understood
understood
understood