Find element that appears once where all others appear thrice | One Unique Rest Thrice
Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the problem one unique rest thrice using bit manipulation where we are required to find an element in array that appears once where all the others appear thrice. In this problem,
1. You are given an array of numbers.
2. All numbers occur thrice in the array except one.
3. You have to find the element that occurs once.
To submit the question, click here: www.pepcoding.com/resources/d...
For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
#bitmanipulation #bits
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Пікірлер: 148
By far the best explanation...It doesn't work with negative values. To make it work, instead of taking INT_MAX, take -1, it'll have all bits set to 1
@SURESHKUMAR-bq8ho
2 жыл бұрын
Yeah!!
@vishantsandilya3482
2 жыл бұрын
awesome brother
@anishkumargiri9490
Жыл бұрын
you saved us man!!
@ferrarif8384
Жыл бұрын
how does it work if we take the value as -1 instead of INT_MAX
@vrajeshbadgujar
Жыл бұрын
Thanks
I don't think anyone can explain this question better than way Sumeet sir has explained. Thank you Pepcoding🙏
Won't lie, this is one of the most beautiful explanations. This not just explains what to do for 3 repeated, but we can extend the same approach for n repeated. Just have to maintain n temp masks and perform circular operations.
Thanks for the best explanation I have ever come across on this problem!
@user-fq1nn1vc2p
9 күн бұрын
Brooo u rocked it yar !
Sir I'll be honest you are one of the best teachers I have met in my life on Internet. Thank you
MIND BLOWING SIR!! MOST CRYSTAL AND CLEAR EXPLANATION FOR BIT MANIPULATION I HAVE SEEN EVER!!
Itna difficult concept itna easily kon samjata ha . Bhai GOOGLE REVIEW bhi likh aya itna acha laga
Humble obeisance for this wonderful explanation....
Belated Happy Teacher's day sir🎉 Putting so much effort for providing free content 🔥
@Pepcoding
3 жыл бұрын
agar aapko mza aya to kya aap google pe hmara ek review daal sakte hain www.google.com/maps/place/PepCoding.com/@28.6993713,77.1360927,17z/data=!3m1!4b1!4m7!3m6!1s0x390d03d054d3e717:0x4fd0fdfc3f27ffaf!8m2!3d28.6993666!4d77.1382814!9m1!1b1
Simply the best explanation 🙌
Dhnayawad Sir Ji
Thanku so much sir Splendid ! 🙏🙏
wow, appreciable explanation of concept.. Thanks 😀
Best explanation !
thank you so much for this explanantion sir!! Understood the concept very clearly.hats off to u for putting this content for free.
@Pepcoding
2 жыл бұрын
You are most welcome For better experience and well organised content visit nados.io
The idea of circular shift is great. I initially thought of using xors and got carried away. Thanks for helping me.
@Pepcoding
2 жыл бұрын
Happy to help! Keep learning. And for better experience and well organised content visit nados.pepcoding.com
Really good explanation. Thanks
wonderful explanation
Amazing! great explanation
Wow who would give all this content just for free.. amazing effort
very nice explanation sir..
Great Sir ❤️❤️ finally ab smjh aaya ki krna kaise h...or hua kaise..... ❤️❤️
@Pepcoding
3 жыл бұрын
Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Very nice explanation!!
the best explanation in this world.
@Pepcoding
3 жыл бұрын
can you review us on google? or maybe write a linkedin post? Thanks, Sumeet Malik
Great explanation..
amazing explanation....sumeet sir >>>>>>>>>
Hello people ..whoever is trying out the solution and it is not working for them when the answer comes out to be a negative number just make sure that you take tn to -1 and not INT_MAX as -1 is the number which has all bits set to 1 and not INT_MAX. Reference video : kzread.info/dash/bejne/qGpmq62eetfQYM4.html Go to 32:53 and see the range. Thank You
@rounakagrawal4760
2 жыл бұрын
Thanks
@shameekpathak8236
Жыл бұрын
this comment should be pinned.
@vinayjangra1401
Жыл бұрын
Thanku so much bro 🤩🤩🤩🤩🤩🤩🤩🤩🤩🤩🤩🤩🤩🤩🤩🤩🤩🥳🥳🥳🥳🥳🥳🥳🥳🥳 initially it was not working on Leetcode, but now it's working 🥳🥳🥳
the concept indeed is explained in the best way possible
@Pepcoding
3 жыл бұрын
agar aapko mza aya to kya aap google pe hmara ek review daal sakte hain www.google.com/maps/place/PepCoding.com/@28.6993713,77.1360927,17z/data=!3m1!4b1!4m7!3m6!1s0x390d03d054d3e717:0x4fd0fdfc3f27ffaf!8m2!3d28.6993666!4d77.1382814!9m1!1b1
@kanhamishra1630
3 жыл бұрын
@@Pepcoding done h sir
I am very happy that you are back
@Pepcoding
3 жыл бұрын
So am I. I love this work so much. The last 5 days were hell. I had to leave this for tax work. Ab nahi jaenge dobara jab tak majboori na hogi.
for updating the tn,tnp1,tnp2 we can simply use the XOR instead of doing the complement and then doing AND , like for tn, we can do tn = tn ^ cwtn instead of tn = tn & (~cwtn) likewise. btw great explanation
A slight variation of the question can be that there can be two numbers which are appearing once So, if the set bit cnt is of 3n nature then for both numbers bit is off if the set bit cnt is of 3n+1 nature then one of the numbers bit is on and if it is of 3n+2 nature then for both numbers bit is on
best explanation
Sumeet sir, U r God !
hats off shirts off everything off for you man!
int tnp1 = 0, tnp2 = 0; for(int i : nums){ tnp1 = (tnp1^i) & ~tnp2; tnp2 = (tnp2^i) & ~tnp1; } return tnp1; here is the simplest form
Amazing😍🤩
In the variable 3n all the bits should be 1 which is (3n = -1) not INT_MAX because in INT_MAX left most bit is 0. It may cause problem in test case having all the negative values. Great explanation though. Correct me if I am wrong.Thanks
@manusingla6446
2 жыл бұрын
So ,bro what we can do in negative values..
@_overide
2 жыл бұрын
@@manusingla6446 take -1 instead of INT_MAX
@manusingla6446
2 жыл бұрын
@@_overide gott it
@trevorPhillips284
2 жыл бұрын
@Pepcoding pin this comment
wow, great explanation!!!!!
@Pepcoding
3 жыл бұрын
Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
@rak590
3 жыл бұрын
@@Pepcoding how do we modify this for negative numbers ?
Maza aaaaa gya sir😅
I am very happy that you are back thankyou so much sir nd your teaching style is amazing bore to kbhi ho hi nhi sakte continue 5 to hrs tk padhai ho jati sir dev bhi aap hi padha djiye na...
@Pepcoding
3 жыл бұрын
agar aapko mza aya to kya aap google pe hmara ek review daal sakte hain www.google.com/maps/place/PepCoding.com/@28.6993713,77.1360927,17z/data=!3m1!4b1!4m7!3m6!1s0x390d03d054d3e717:0x4fd0fdfc3f27ffaf!8m2!3d28.6993666!4d77.1382814!9m1!1b1
@sukanyasinha3583
3 жыл бұрын
@@Pepcoding sure sir aapke liye to ache reviews bante hai mai zarur dungi sir mjhe aapki class join krni hai
@sukanyasinha3583
3 жыл бұрын
@@Pepcoding done sir
@amandixit3555
3 жыл бұрын
@@sukanyasinha3583 very good
Amazing🔥👌
@Pepcoding
3 жыл бұрын
Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Ek no.
approach is booming at -ve test cases.
@Pepcoding
2 жыл бұрын
Visit - nados.pepcoding.com and sign up to NADOS. Don't forget to follow us on Instagram instagram.com/pepcoding/
tn = -1 for negetive test cases
sir this approach is not working if numbers are negative
This question should be of hard level (but it is rated medium) if done in time complexity of O(N) and space complexity O(1).
Amazing!!
@Pepcoding
3 жыл бұрын
beta please ek google pe review daal do g.page/Pepcoding/review?rc
@ankitamehra5045
3 жыл бұрын
@@Pepcoding done!
my head hurts but i understood everything now .
Very proper explanation!!
@Pepcoding
3 жыл бұрын
Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
some dp questions that are no where on leetcode , like some challenging google DP questions from the student experiences and all
@Pepcoding
3 жыл бұрын
Sep 25 tak poore 200 questions honge site pe DP ke
@AnkitSingh-zj2uc
3 жыл бұрын
@@Pepcoding waiting 🤩
Why can't we do simply (sumSets*3-sum)/2 thats also O(n+log(n))≈O(n). Will also not create any problem for negetive numbers in the array.
why can't we take an xor instead of taking an and with the one's complement, since we need to toggle the set bits
All video playlist ? Please
@Pepcoding
3 жыл бұрын
www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup/bit-manipulation yahan se kijie
bada teekha sawal tha 2 baar dekhna pada
@Pepcoding
3 жыл бұрын
hanji teekha hai
Amazing 🔥
@Pepcoding
3 жыл бұрын
agar aapko mza aya to kya aap google pe hmara ek review daal sakte hain www.google.com/maps/place/PepCoding.com/@28.6993713,77.1360927,17z/data=!3m1!4b1!4m7!3m6!1s0x390d03d054d3e717:0x4fd0fdfc3f27ffaf!8m2!3d28.6993666!4d77.1382814!9m1!1b1
@rahulbhatia3075
3 жыл бұрын
@@Pepcoding sure sir
@rahulbhatia3075
3 жыл бұрын
Done sir
@adityasrivastava7956
3 жыл бұрын
@@rahulbhatia3075 Thanks beta
Brute Force Solution with same complexity as the optimised approach, Time Complexity O(N) Space Complexity O(1) int ans = 0; for (int i = 0; i int count = 0; int mask = (1
@Pepcoding
2 жыл бұрын
For better experience, visit nados.io, where you will get well curated content and career opportunities.
[2,2,-3,2] it is not handled by last approach if ans is negative
@Pepcoding
3 жыл бұрын
Lemme check it again.
@suchitragiri4546
3 жыл бұрын
@@Pepcoding hmm its fail in this tc
@samchau8011
3 жыл бұрын
@@suchitragiri4546 Yaa it is not working if the answer is negative number
@RajivKumar-qj9nw
3 жыл бұрын
@@samchau8011 take tn = -1 instead of Integer.MAX_VALUE
@samchau8011
3 жыл бұрын
@@RajivKumar-qj9nw Thanks Rajiv.. that's well thought out.. INT_MAX is not the number in which all bits are set rather -1 is the one where all the bits are set!
jo jis sequence m aapne sikaya h uske hisab se code kuch aisa hona chahiye t1 = t1 & (~cwt1); t2 = t2 & (~cwt2); t2 = t2 | cwt1; t3 = t3 & (~cwt3); t3 = t3 | cwt2; t1 = t1 | cwt3; kaam dono same hi krenge
Sir these approach fails in case of negative number ??
@theuntoldtree
2 жыл бұрын
yep, you got better solution?
sir saare 1 then 3n mei toh intially usko INTEGER.MIN_VALUE se nhi krna chaiiye intialize nhi krna chaiye tha
guys take tn as -1 to get rid of error
Sir, ye Ques Leetcode pe submit nhi hora... Negative numbers k liye wrong answer derha h.. Kase handle kiya jae isko please btadijiye.. Leetcode 137 problem number
@harshtekriwal131
3 жыл бұрын
Because in integer.max_value , the 32th bit is 0, as it is a positive number , create a bit mask with all 32 bits on. The number representing all 32 bits on is -1.
@anishsuman1371
3 жыл бұрын
@@harshtekriwal131 thanks
sir the approach fails for the negitive values in the array ,do tell the reason and the cure ,Thanks a lot for the effort sir
@Pepcoding
3 жыл бұрын
Thank you so much and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Gold
@Pepcoding
3 жыл бұрын
Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
areeee sir g. (ekk hi dil hai .pta nahi kitne times loge)
@Pepcoding
3 жыл бұрын
agar aapko mza aya to kya aap google pe hmara ek review daal sakte hain www.google.com/maps/place/PepCoding.com/@28.6993713,77.1360927,17z/data=!3m1!4b1!4m7!3m6!1s0x390d03d054d3e717:0x4fd0fdfc3f27ffaf!8m2!3d28.6993666!4d77.1382814!9m1!1b1
@nishantsharma8776
3 жыл бұрын
@@Pepcoding you are our mentor. So don't use could or can..we can do anything for you
ekdm umdaa explanation.
its not working for negative numbers
Am I the only one who is not able to understand about the why part of logic. Edit: after watching the whole video I take my prev words. The instructor never disappoints. He is awesome in explaining. I used the logic which he gave and programmed it, passed every test on leetcode. But yeah why we were initialising the initial 3n , 3np1 and 3np2 is not clear yet.
@Pepcoding
2 жыл бұрын
For better insight, visit nados.io, post your doubts, community will help you out there.
@VY-zt3ph
2 жыл бұрын
@@Pepcoding okay. I loved this video by the way. Your whole bit manipulation playlist is elixir.
Sir pls pls aapse ek request hai string par kuch material de djiye na pls pls pls
@Pepcoding
3 жыл бұрын
bass beta bhot jald dalunga. Oct 30 tak ho jaega.
@sukanyasinha3583
3 жыл бұрын
@@Pepcoding ok thankyou sir aap bol diye bas bhut hai aap itne hardworking ho aap bhut ache content dnge I know.
❤️
you re back m to darr gya tha ki ap upload krna band na kr do😥
@Pepcoding
3 жыл бұрын
arey, majboori mei gya tha. kaam nipta ke asli kaam pe waapis. agar aapko mza aya to kya aap google pe hmara ek review daal sakte hain www.google.com/maps/place/PepCoding.com/@28.6993713,77.1360927,17z/data=!3m1!4b1!4m7!3m6!1s0x390d03d054d3e717:0x4fd0fdfc3f27ffaf!8m2!3d28.6993666!4d77.1382814!9m1!1b1
@prathamjagga5597
3 жыл бұрын
@@Pepcoding done sir 👍
Sir mai pepcoding ke baare me ek post kardunga Linkedin pe mere 600 followers hai ,aap bas free content daalte rehna aur course poora karna : )
@Pepcoding
3 жыл бұрын
ji bilkul
@Pepcoding
3 жыл бұрын
agar aapko mza aya to kya aap google pe hmara ek review daal sakte hain www.google.com/maps/place/PepCoding.com/@28.6993713,77.1360927,17z/data=!3m1!4b1!4m7!3m6!1s0x390d03d054d3e717:0x4fd0fdfc3f27ffaf!8m2!3d28.6993666!4d77.1382814!9m1!1b1
@InvestInIdeas
3 жыл бұрын
@@Pepcoding kardiya sir 5 star de diya
giving wrong answer in case of negative element in the array...
@blueranger3099
3 жыл бұрын
bhaiya correction toh bata do, like krke chle gaye😂
@LegitGamer2345
3 жыл бұрын
comments mai kisine iska solution diya hai
sir apke method bada hi confuse kar dete hain, yeh wala dekh ka r dimag hi kharab ho gaya hai, auro ko samajh mei aa gayi, mujhe hi nahi aayi, then i find a way to do it in O(logn) complexity, i think mujhe zyada practice ki zaroort hai
@Pepcoding
3 жыл бұрын
beta, ye wala solution to kaafi cleanly done hai. aap is question ki video dekhkar araam se ise 1 ghnte mei master kar sakte hain. geeks ka solution iske muqable kaafi khraab hai
@amandixit3555
3 жыл бұрын
samajh aa gaya sir, jinda baad jinda baad......
Is this method is works on negative numbers or not
itna lengthy video he last tak jate jate me sab bhul gaya .
@Pepcoding
2 жыл бұрын
We request to give it a chance, it is actually very thorough. For doubt support on videos check nados.pepcoding.com