Count Triplets That Can Form Two Arrays of Equal XOR | Leetcode 1442 | codestorywithMIK
Vložit
- čas přidán 6. 09. 2024
- iPAD PDF Notes - github.com/MAZ...
Whatsapp Community Link : www.whatsapp.c...
This is the 16th Video of our Playlist "Bit Manipulation : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a good Bit Manipulation Problem : Count Triplets That Can Form Two Arrays of Equal XOR | Multiple Approaches | Leetcode 1442 | 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 : Count Triplets That Can Form Two Arrays of Equal XOR | Multiple Approaches | Leetcode 1442 | codestorywithMIK
Company Tags : will update soon
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
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/MAZ...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Initialization:
We create a prefixXor array of length arr.length + 1 to store the cumulative XOR values, with the first element initialized to 0.
Computing the prefix XOR:
The for-loop computes the cumulative XOR up to each index i and stores it in the prefixXor array. This is equivalent to the C++ operation with the prefix XOR computation.
Counting the triplets:
Nested loops iterate over all pairs (i, k) where i less than k. If prefixXor[k] is equal to prefixXor[i], it means the XOR of the subarray arr[i] to arr[k-1] is 0. We then count the number of valid j values (i.e., j between i and k), which is k - i - 1.
✨ 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 #newyear2024
if somebody is confused that how if a1^a2^a3^a4=0 then a1=a2^a3^a4, a1^a2=a3^a4... and all other combinations-
given: a1^a2^a3^a4=0
take xor of a1 both size
a1^a1^a2^a3^a4=a1
0^ a2^a3^a4=a1
and a2^a3^a4=a1.... similarly for others
Thank you for this comment ❤️❤️
thanks man
👍🏻
good one
do we Really Need prefix array ?
class Solution {
public:
int countTriplets(vector& arr) {
int n = arr.size();
int res = 0;
for(int i = 0; i < n ; i++){
int a = arr[i];
for(int k = i + 1; k < n ; k++){
a ^= arr[k];
if(a == 0)
res += (k - i);
}
}
return res;
}
};
I agree. We don’t need that.
@@codestorywithMIK i did the same solution and i also think the same why you said for 2nd approach that it is O(n3)
Ideally the second loop should start from k=(i+2) this will ensure we are just finding valid triplet,however in this question our constraints are such that arr[i] can never be 0 so it will automatically ensure no two consecutive prefixXor are same so in this case its also working for k=(i+1). Thank you for such nice explanation.
That’s a very good point.
Thank you Roshan ❤️
correct
nice observation !!
class Solution {
public:
int countTriplets(vector& arr) {
int n = arr.size();
int pairs = 0;
for(int i=0; i
public int countTriplets(int[]arr){
int triplets=0;
for(int i=0;i
3rd approach is very clever.
Definitely need meticulous observation to come up with such an elegant solution.
When do you wake up ? When do you make videos 😮
Surely, as early as 5AM. He's a different level of dedication.
@@akshaychavan5511 yeah, he is a legend
brute force :
class Solution {
public:
int countTriplets(vector& arr) {
int count = 0;
for (int i = 0; i < arr.size() - 1; ++i) {
int xorA = 0;
for (int j = i + 1; j < arr.size(); ++j) {
xorA ^= arr[j - 1];
int xorB = 0;
for (int k = j; k < arr.size(); ++k) {
xorB ^= arr[k];
// found a triplet (i, j, k)
if (xorA == xorB) {
++count;
}
}
}
}
return count;
}
};
❤️🙌
thanks for the regular videos man, really appreciated. Btw, cooker mai 3 se zada seeti lag gayi bhai, hopefully hamare liye videos banane ke chakkar mai aapka rajma overboil na ho gaya ho ;)
😂
😅 Rajma was good ❤️
I don't think we need to store the prefix xor we can store the i and k in a variable and check if the variable is zero or not if zero we can add that into our count. adding the for code for better understanding. and Thanks for the explanation bro. class Solution {
public int countTriplets(int[] arr) {
int count = 0;
int n = arr.length;
for(int i = 0; i < n; i++){
int a = arr[i];
for(int k = i+1; k < n; k++){
a ^= arr[k];
if(a == 0){
count += (k-i);
}
}
}
return count;
}
}
Indeed ❤️
class Solution {
public:
int countTriplets(vector& arr) {
int n = arr.size();
int ans=0;
for(int i=0; i
prefixSum ki prefixXor related bhi problems ho sakte hain ye socha nahi tha maine. Good thing to learn .
Bhaiya sorting pe videos kab aayegi (Selection, bubble)????
Do you mean, the sorting algorithms , their working, time complexities etc ?
@@codestorywithMIK exactly
Thank you Sir!! Prefix Xor approach was awesome
(2143ms) BRUTE FORCE IN JAVA:
class Solution {
public int countTriplets(int[] arr) {
int ans = 0;
for(int i = 0; i < arr.length; i++){
for(int j = i + 1; j < arr.length; j++){
for(int k = j; k < arr.length; k++){
if(xor(arr, i, j - 1) == xor(arr, j, k)) ans++;
}
}
}
return ans;
}
int xor(int[] arr, int idx1, int idx2){
int xor = 0;
for(int i = idx1; i < idx2 + 1; i++){
xor ^= arr[i];
}
return xor;
}
}
O(n) c++ solution
class Solution {
public:
int countTriplets(vector& arr) {
int n = arr.size();
unordered_map pos;
pos[0] = {1, -1};
int count = 0;
int Xor = 0;
for (int i = 0; i < n; i++) {
Xor ^= arr[i];
count += (i - 1) * pos[Xor].first - pos[Xor].second;
pos[Xor].first++;
pos[Xor].second += i;
}
return count;
}
};
Perfect
Thanks for putting effort. That’s how we will grow ❤️❤️❤️
public:
int countTriplets(vector&arr){
int ans=0,n=arr.size();
vectorprefXor(n+1,0);
unordered_mapsumOfi,countOfXor;
sumOfi[0]=0;countOfXor[0]=1;
for(int k=1;k
@Pankaj.032 hello bro, could you please explain this line "count += (i - 1) * pos[Xor].first - pos[Xor].second;". I am not getting the logic behind this line.
Brute force solution in java
class Solution {
public int countTriplets(int[] arr) {
int n = arr.length;
int count = 0 ;
// We can use three for loop for brute force approach
for(int i = 0 ; i < n ; i++){
for(int j = i+1 ; j < n ; j++){
// since we have to find the two values
// i to j == a
// j to k == b
// if the value of a == b | increment the count
int a = 0 ;
for (int k = i ; k < j ; k++){
a ^= arr[k];
}
int b = 0 ;
for (int k = j ; k < n ; k++){
b ^= arr[k];
if (a == b){
count++;
}
}
}
}
return count;
}
}
Correct me if I'm wrong bhaiya. The optimal approach is still taking O(n^2) time and O(n + 1) extra space for the prefix array. So why don't we just avoid prefix array and simply do the following:
class Solution {
public int countTriplets(int[] arr) {
int n = arr.length;
int cnt = 0;
for(int i = 0; i < n; i++){
int xor = arr[i];
for(int k = i + 1; k < n; k++){
xor ^= arr[k];
if(xor == 0){
cnt += k - i;
}
}
}
return cnt;
}
}
Here, TC = O(n^2) and SC = O(1). Please corerct me if I'm missing any minor detail.
O(n) c++ solution
class Solution {
public:
int countTriplets(vector& arr) {
int n = arr.size();
unordered_map pos;
pos[0] = {1, -1};
int count = 0;
int Xor = 0;
for (int i = 0; i < n; i++) {
Xor ^= arr[i];
count += (i - 1) * pos[Xor].first - pos[Xor].second;
pos[Xor].first++;
pos[Xor].second += i;
}
return count;
}
};
@@Pankaj.032 why should I use a map? It adds an extra space. My solution works in O(1) space. @codestorywithmik bhaiya can you please reply back?
@@jewelchakraborty9717 this code is using O(n) time and space
whats the need of this prefix xor array when we are solving it in n square we can directly take runing xor for the inner loop
I agree. You can still solve it in O(n^2) without prefixXor. But yeah, it will be good to know that prefixXor can be used in problems like these ❤️❤️
Actually bhaiya , i
Brute Force :
int countTriplets(vector& arr) {
int ans = 0;
int n = arr.size();
for(int i = 0; i
❤️👌
Thanks a lot. got to learn new things
please explain the o(n) approach also
I solved it using map.
It’s very similar to finding sub arrays having sum = 0
Pls give code
@@k-CE-OmkarPathak
class Solution {
public:
int countTriplets(vector& arr) {
int n = arr.size();
int triplets = 0;
unordered_map mp;
mp[0] = {1,-1};
int prefixXor = 0;
for(int i=0;i
@@vamsimadugula8524 Thanks
// brute force approach
int count=0;
for(int i=0;i
❤️❤️❤️
Nice explanation
love you bro
can you explain the logic of 'k-i'. Like how does it tell you number of triplets
k-i just gives the length of the portion from i to k
And now in this portion you have multiple options to put j pointer.
This gives the possibilities of getting triplets.
class Solution {
public:
int countTriplets(vector& arr) {
int n = arr.size();
int triplets = 0;
unordered_map mp;
mp[0] = {1,-1};
int prefixXor = 0;
for(int i=0;i
Thanks bhai . very well explained
Bro pls make a playlist on Bit Manipulation
Maza aaya
Brute force:
class Solution {
public int countTriplets(int[] arr) {
int count=0;
for(int i=0;i
// brute force solution
class Solution {
public:
int countTriplets(vector& arr) {
int count = 0;
for(int i = 0;i
Hello bhaiya maine to just subarray se hi kar liya ::---
O(n^2) :)
class Solution {
public:
int countTriplets(vector& arr) {
int mx=0;
int n=arr.size();
for(int i=0;i
Yes .That is correct too ❤️
Thanks a lot bhaiya ❤❤
It's working for a few test cases, but I can't identify why it's failing. Please help!
class Solution {
public:
int countTriplets(vector& arr) {
vectorprefix(arr.size(),0);
prefix[0]=arr[0];
for(int i=1;i
cooking dal in background👍
😅❤️
Done✅
MIK how are you able to calculate xor so quickly? 🏎
Actually I solved those test cases multiple times. It was in my head for a while 😅
Bro aap konsa device use krte ho pentab vgara ke lie
can this be done by sliding window ?
Sir dp series please 🙏🏻
Let me try this weekend ❤️
class Solution {
public int countTriplets(int[] arr) {
int c=0;
for(int i=0;i
Why does Leetcode accept brute force approach?
Just because the constraints were small for this qn
brute:
class Solution {
int makeXor(vector& arr, int l, int r){
int res = 0;
for(int i=l; i
Fod diya question 🎉
Thank you 🙏😇
o digital notes send karo na pl
iPAD PDF Notes - github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad%20PDF%20Notes/Leetcode-1442.pdf
title name is wrong leetcode code number wrong
I think they are correct. Where you are referring ?
Can you please confirm ❤️
@@codestorywithMIKIt's 1442 not 1424
@@codestorywithMIK In title it says 1424 but actually it is 1442
yes videk title it should be 1442
Corrected.
Thank you ❤️❤️❤️
H.W
(Yahi krna tha?)(or kuch hona h toh pls btao sir)😅
class Solution {
public: int countTriplets(vector& arr) {
unordered_mapmp; //xor,index
mp[0].push_back(0);
int n=arr.size(),Xor=0,ans=0;
for(int i=0;i1){
for(int i=0;i
Awesome ❤️
@@codestorywithMIKbhaiya time complexity btado pls help
Done ✅