Single Number III - Leetcode 260 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem single number three this is a fun one and I really wish they gave it to us yesterday cuz it's definitely easier than yesterday's problem though it's definitely not easy so the idea is we're given an input array of numbers every single number shows up twice except two numbers in this example this input array these are the two numbers that don't show up twice and obviously these two numbers have to be different from each other if they don't show up twice they only show up a single time each if they were not different then obviously they would show up twice so those are kind of the assumptions now we want to identify which two elements don't show up twice and we want to return them in the form of an array we can put that array in any order that doesn't matter now the easiest way to solve this problem is pretty much with a hashmap right just count the occurrences of every single number all of them will show up twice except for a couple of them and then those ones that only show up once so we'll have three mapped to one and five mapped to one these are the two elements we're going to return that's obviously a linear time solution and a linear space solution the only catch is that it's actually possible to solve this problem without using extra space and in linear time if they said we can't use extra space then my proposal would be Let's do an O of N2 solution even though you always want to avoid those if we can have like linear time Solutions even if the linear time solution takes extra space but there is an N squ solution maybe you can think of it it's pretty much just nested Loops right so for every single number start here check does that number show up anywhere else yes it does so skip it next number does it show up anywhere else yes it does skip it this number also shows up somewhere else and that kind of indicates to you that we're not just looking for elements to the right we're actually going to be searching through the entire array and then we do the same for this one and this one we'd see actually doesn't show up twice so let's add this to our result it's going to be an array let's add three to the result and then finally we'd see two shows up twice five does not and then that would be the result N squared solution nested Loops but constant space but we can do better the idea is similar to yesterday obviously we know the way exor math Works a number exord with itself is going to result in zero they cancel out like two in binary looks something like this and if we exort it together we look at this they're the same bits we get zero same bits zero same bits zero exclusive or right we're looking for different bits we also know that the order in which we do the exors doesn't really matter so if we were to take this entire set and xor all these numbers together what would be the result well like I said numbers will cancel each other out the same number so we know there's a duplicate of these duplicate of these so therefore the result of the entire exor should be 3 xord with 5 but how does that help us like can we extract the information from this let's consider it what does three look like in binary it looks I think like this and then five I think is this so and the rest of these will be zeros so if we were to exort these two numbers when they're the same we're going to get zero same we're going to get zero same over here as well we're going to get zero and this is kind of a pretty important point this is why we can't use the result because look we had two zeros here and we got a zero in the output we had two ones here and we also got a zero in the output so how do we know were there zeros in both spots or were there ones in both spots we don't know but we do know here that we got a one here and we got a one over here this is surprisingly very useful information because a one bit in this spot tells us that only one of these numbers had a one bit in that spot we don't know which one it was that's unfortunate but one of them did and same thing in this spot one of them had a one bit now obviously in this case they're different so we don't know like were they the same maybe this one had a one and this was a zero we don't know so that's kind of the difficult part my goal in the next few minutes is to give you enough intuition that you can actually implement the code yourself but even if you can't that's okay cuz I'll walk you through it as well hypothetically speaking we know these two are the results wouldn't it be nice if we could take this number and then exort it with a bunch of pairs like not just exort it with a one but exort it with both of the ones and not just exort it with one of the twos but exort it with both of the twos if we could do this xor we would obviously result with just three itself if there was some way to isolate three and five to separate them out wouldn't that be kind of nice and maybe it doesn't even have to look like this it could also just look like three exord with both of the ones or three exord with both of the twos and then five would be exord with both of the ones or maybe you know five would just be by itself if three took all the other numbers so is there a way to divide the remaining numbers like we already know well we don't know what these are but these are the ones we're looking for we also know there's a bunch of remaining numbers is there a way to divide both of these out into two separate groups based on some condition the only thing we need to make sure of is that the same number does not appear in separate groups the same number must belong to the same group is there a way to do that my hint to you is we can use this idea here and if it still doesn't make sense let me add one more point in these two groups one thing needs to be sure the same number cannot show up in both groups the same number must belong to the same group and the second thing more importantly is that this has to go in one of the groups and this has to go in the other groups doesn't matter which like this could have gone in this group and this could have gone in that group it doesn't matter which but this has to go in a different group and this has to go in a different group because we know if we exort all those together the result is going to be three if we exort all these together the result is going to be five how do we do it how do we make sure three goes in this and five goes in that well very very simple the differing bit we identifi that there's two bits where they have a different spot we're guaranteed that at least one position is going to have a different bit otherwise these two numbers would be the same right so we don't care which of these bits we use we could use this one or we could use this one it doesn't matter I'm just going to arbitrarily pick this one I've uh drawn these out just to kind of show you the binary represent ation of each of these but let's focus on this bit it's the second bit what we want to do is just have this bit so we're going to consider the number that looks like this 0 0 1 0 it happens to be the number two that's not super important just the fact that we isolated this bit so now the way we're going to separate these values is every single number that has a one in this spot is going to go in group a let's call it and every number that has a zero in this spot AKA does not have a one in this spot is going to go in group b this criteria is enough for us to guarantee that three remember this is the number we want to go in this group and five is going to go in the other group all the other numbers it doesn't matter does one go in this group or does it go in the other group it doesn't matter cuz there's two ones there's two of them so they're going to cancel each other out anyway doesn't matter which group two goes in there's two of them they're going to cancel each other out anyway but this is the beautiful solution where exor will solve it in linear time so let me just take like 30 to 60 seconds dry run through this does one have like a bit set in that spot it does not so it's going to go in group b does two have a bit in that spot it does it's going to go in group a and then one we already know it's going to go in group b and then three that's uh the interesting case three of course it has a one in that spot so it's going to go in group b three over here now lastly a two is going to go in the first group and five is not going to have a bit set in that spot and so it's going to go in group a remember all of this is the result we know these two numbers had different bits we don't care which one had a one we don't care which one had a zero we don't even need to know that we solved it by do doing this if we exor all these together a is going to be five exor these together B is going to be three and we can just put these two in an array and then return it obviously linear time obviously constant space these are not hash Maps we're going to be exhorting numbers as we add the numbers to like each of these so you'll see that in the code so let's do it like I said first things first we just want to take every number in the input and exort them together that's going to give us all the numbers exort together and so we just want to find one of the differing bits now you can calculate that multiple ways like there is a shortcut to do that I'm not going to go into that cuz I really don't think it's that important it's not too difficult to get a differing bit let's just start with one so we obviously know that this like in terms of binary looks something like this and so what we're going to say is take the exor number here and take the bitwise and with the current differing bit candidate so this and if bit because what that's going to do is suppose that exor number is something like this right so if we take this and and it with this we know that these are all zeros so the output is going to be zero after ending so those are all going to be zeros but here we're just checking this bit is it the same as this one are they both one nope so that's a zero so this would fail while it's failing so while not so while this is false then we're going to continue now we want to try the next one we want to try the next bit so instead of having a one here I'm going to put the one in the next spot I'm going to shift it to the left so all I have to do here is say diff bit set it to itself and shift it to the left by one and now we'll try again and this with this we know all these are going to be zeros we know this one is going to be zero as well we only look at this bit is it the same as this one yes it is there's a one in the output therefore this is non zero it evaluates to true we know we can stop sh sh ing this we found the bit that we're looking for so that's kind of the logic behind that and now that we have that number we want to get our groups A and B initially let's set them both to zero these are what we're going to return just like this and now I'm going to say for every number in the input if the diff bit is also set in the current number n how do I check that well that's literally what we just did up here so we're going to take this bit is it set in this number bitwise and like this if it is let's just add it to group a we could have done Group B but it doesn't really matter and when I say add it to group a I mean take a and exor it with the current number and otherwise we'll add it to Group B say this then we're done the entire solution it looks pretty simple doesn't it but it's not so don't like fool yourself this is not easy to come up with let's run it though and as you can see we are at the tippy top this time at least if you found this helpful check out N.O for a lot more thanks for watching and I'll see you soon