Sum of All Subset XOR Totals | Simple Story To Code | Leetcode 1863 | codestorywithMIK
Vložit
- čas přidán 1. 06. 2024
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 39th Video of our Playlist "Leetcode Easy : Popular Interview Problems" by codestorywithMIK
Subsets - • Subsets | Simple Story...
In this video we will try to solve an easy bit-magic Problem : Sum of All Subset XOR Totals | Simple Story To Code | Leetcode 1863 | 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 : Sum of All Subset XOR Totals | Simple Story To Code | Leetcode 1863 | codestorywithMIK
Company Tags : Google, Meta
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/sum-of-...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Using Simple Backtracking to Generate Subsets
**Time Complexity**: O(n * 2^n)
**Space Complexity**: O(n * 2^n)
In this approach, we use backtracking to generate all possible subsets of the input array `nums`. We recursively build subsets by either including or excluding each element. Once all subsets are generated, we iterate through each subset to compute their XOR sums and accumulate these results.
This method is straightforward and easy to understand, but it has higher time and space complexity due to the need to store all subsets.
Approach 2: Using Optimal Backtracking
**Time Complexity**: O(2^n)
**Space Complexity**: O(n)
In this approach, we use an optimized form of backtracking that calculates the sum of XORs of all subsets without explicitly generating the subsets. Instead, we recursively compute the XOR sums by either including or excluding each element and sum up the results directly.
This method is more efficient in terms of space since it does not need to store all subsets. It leverages recursion to directly compute the required sum, reducing the overall space complexity.
Approach : Using Pattern
The provided solution calculates the sum of the XORs of all subsets of an integer array efficiently by leveraging bitwise operations. Here’s a concise summary of the approach:
1. **Bitwise OR Calculation**: The solution first computes the bitwise OR of all elements in the array. This captures all the bits that could possibly be set in any subset.
2. **Shift Operation**: The result of the OR operation is then left-shifted by `(n - 1)` positions, where `n` is the number of elements in the array. This accounts for the fact that each bit's contribution appears in multiple subsets.
This method simplifies the problem by avoiding the need to explicitly generate and XOR each subset, achieving a linear time complexity relative to the number of elements in the array. The approach takes advantage of the properties of XOR and the combinatorial structure of subsets.
Short summary on Why This Works : The sum of the XORs of all subsets can be derived using bitwise properties:
Each bit in the result will be set if it is set in any of the elements of the array.
For an array of length n, each subset can include or exclude an element, leading to 2
n−1
subsets that include a particular element in some position.
✨ Timelines✨
00:00 - Introduction
02:22 - Approach-1
09:15 - Approach-2
17:49 - Approach-3
#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 #newyear2024
please make the video on the intuition behind the 3rd appraoch..
yes
exactly bhai kya chu&iyap hai.. intuition dekhne aaya tha behind shifting by n-1. Aur pattern ke name pe skip krdiya
@@theprnvanand to isme gali dene wala logic to kuch nahi hua atleast usne bataya to it's your duty to find it sab kuch hath p nahi milta h bro thoda hath pair chalao google is all yours
Hi guys,
Apologies for any inconvenience. Like I mentioned in the video that I will create a separate video for that in my free times. It’s difficult to make detailed video early morning because of my office and other morning activities.
Hope you guys will understand ❤️🙏
But if I get some free time, I will create a detailed video on why it works.
Thank you again for your patience ❤️
Please make detailed video on 3rd approach
sir i would like to provide one suggestion 🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏
plz add 3 to 4 similar types question it helps alot like we learn from you solve the question and excel ourself with your help so plz do this one i am following you since a month and i am loving you content too much like i am addicted to your content i come i learn i solve and repeat this process
💥❤🔥❤🔥❤🔥❤🔥❤🔥💥💥💥
Respected MIK Sir,
Whenever I watch your videos, I understand how easily & efficiently one can solve difficult questions.
Thank you so much for sharing this knowledge for free. 🙏🏼
how 3rd approach works please make a video on that.
3rd approach is awesome 😅❤
yes need the video on the intuition behind the 3rd appraoch..
Would love an explanation on proof of 3rd approach, if you have time then please consider
Yes , please make a video on how to get this intuition
Did this question using recursion. However, came here to see new approaches and I am quite amazed seeing the 3rd approach. Indeed a tough intuition to come up with.
3rd approch man 👍fabulous.just looking like Wow...
Great Bhaiya, Bhaiya aaj ka question easy marked hai but aise hi question mey mey fass jata hu like mey subset create karke to kiya but Approach -3 wala mujhse nahi hit hua mind mey to ye kaise develop kare, aur phir aise hi problem se moral down ho jata hai ki solve to kiye but best approach nahi tha, and phir self doubt bhi hone galta hai
Bhiya, please post a video of the last approach on the reason of following pattern the last one approach is very awesome.
Bhaiya pls make video why pattern work in the 3rd approach
Sir please the video on the intuition behind the 3rd approach.
this guy will make me fall in love with dsa
Yes, please make a video on 3rd approach.
Day-1 of asking "How do you manage teaching DSA, Office Hours, Doing sports as well as travel and handling social media" 😅
Mik Bhai, ye kar diya approach -3 pura hila diya. Approach - 3 actually blow my mind. But ek kuch explanation do how to build this type of Intuition!
Amazing explanation
Good solution but would have been better if logic behind 3rd approach was also covered in the video, we can watch 1 hr long videos of such amazing content.
finding the last approach is not at all intutive unless you understand that much maths in the interview!
approach 3 was really nice one🔥🔥
Good explanation 👏 👍
Thanks a lot bhaiya ❤❤
Bro please make a video on tarjan's algorithm, Leetcode 1192. Great content brother, lots of respect
please make the video on the intuition behind the last approach please.
Thank u so much ❤
Thank You Bhiya :)
please explain the 3rd approach, any proof apart from obsering patterns.... what's the logic behind it, why it works
bhaiya please give us 3-4 home work questions it would be really helpful
sir plz make a video on detailed explanation of approach 3 🙏
bro what are you plaanning to finish first dp concept or start backtracking concepts
damn good mann!!
3rd approach ke upar video bana dijiye 🙏
how is this marked easy :)
so much to learn....
should I start with recursion and dp first ?
Bhaiya last wale approach ke lie video banado plsssss
Please Explain why the third approach worked!
sir at 5.07 apne by reference num kyu lia usko koi reason h ? and can we use onli auto there
bhaiya video bana dena approach intuition pe
what is intution behind third approach that it works,please explain how it works.
power set algorithm
But can you please explain why the third approach works?
Please Intuiton behind 3rd approach
Done ✔️
I was able to solve using approach-1 on my own 🤩
Thank you
Third approach, albeit simple, is hard to come up with in an interview setting I think.
result
We can also find the subsets using bit manipulation technique
Can anyone explain the intuition behind the 3rd approach?
This can also be done using bit manipulation.
3rd Approach Kaise Socha Sir ????
Sir dp series please
approach 3rd is OR not XOR
?
Bhaiya ❤
Why does the third approach work, Can anybody please share a link or a video for the proof of that
It’s available on official solution but I could not understand. I also saw vortubrac’s leetcode solution in Discuss, but he has not explained it.
man wtf was that last inuition 🤯
sir, it might sound funny, but please its a request help me to understand how can i , iterate vector subset to find all the xor , basically i am asking about approach number one
int xorr=0;
for(int i=0;i
@@YashDabhade-cr5my thanks🙏🙏🙏🙏
No Qn is funny 😇❤️
Don’t worry, you can ask any kind of qn. We all are learning ❤️
@@codestorywithMIK yes sir 😇😇😇
int solve(vector& nums, int i){
if(i>=nums.size()){
return 0;
}
int include=nums[i]^solve(nums, i+1);
int exclude=0^solve(nums, i+1);
return include+exclude;
}
int subsetXORSum(vector& nums) {
return solve(nums, 0);
}
why this is incorrect