Minimize XOR - Leetcode 2429 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimize exor and this is one of those problems when you actually draw it out like at first it seems like a difficult problem but when you start to actually draw it out and like think about it it becomes pretty straightforward in my opinion the idea is that we're given two different numbers so N1 which is uh three and I'll draw it in a binary I think it'll be something like this and we are also given five which I believe in binary will be 4 + 1 so what we're trying to do here is find some positive integer X and there's a couple things that we want to follow here one is that this number X its binary representation has to have the same number of set bits as N2 so this means that this number here is five it looks like it has two bits that are set thus whatever number we pick for x X it has to have at most only two bits set and in fact it has to have exactly two bits set so no more and no less than two they could be in any position like we could put them like this but it has to have it exactly two bits set now the second part here is where exactly we are going to put the bits we technically can't put them anywhere that we want because what we're trying to do here is minimize the exor of the number X that we pick exord with N1 here so we're trying to minimize this result the way to interpret uh this condition here is basically to know that first of all what does xor actually mean well if we pick some number let's say I pick this number 1 0 0 it has the exact same number of bits as N2 it has two bits set just in different positions we could have picked any of the positions but these are the ones that we picked now what we want to do is minimize the exor of this and this well what does an exor between these two look like in the first place let me just draw the number here 0 0 1 1 and now if you exort each of the spots basically if they're different we're going to have a one here if they're the same we're going to have a zero in the output now these are different in every spot so we're going to have a one in all four positions what we were trying to do is minimize the exor of these two numbers now as you can see the fact that they were different made the xor of them maximal so the way to have minimized this exor would have been to have had the same number uh in this spot so this is the number that we could have chosen we could have chosen a 0 01 1 in that spot and then the exor of it with that would have been all zeros so this is kind of the way to interpret this second condition by making this exor minimal what we're trying to do is make X as similar to N1 as possible if we could we would literally use the same exact number we would use 0011 for this example so why would we not be able to do that because in this example we have this second number which tells us we need two bits and this number tells us we want it to be as similar to this as possible which has exactly two bits set so in this case we can make it exactly like this now what if I change this second number N2 to be this if I add a one over here which I believe will make this a seven now how does that change the problem well I need exactly three bits to be set I want it to be as similar to this number as possible so I'd like it to be this but I need three bits set and right now I only have two in this number so I want to set at least one more bit or exactly one more bit in this case so where should I set it should I set that bit over here over here maybe somewhere further to the left well what we're trying to do is with this number and the number that we pick we want the exort to be minimal so we should probably choose the least significant bit because we know the bits are going to be different in that spot and thus the resulting bit is going to be different in that spot so we should probably set the least significant bit in this uh position so our starting point for X will be N1 which is this and we count that there's two bits here but there are three bits in the Target or like the number that tells us how many bits we need and thus we will find in this number the least significant position with an unset bit and then set that bit and we will just do it one time because we only needed one extra bit but you can imagine if this had four bits set well then we would have done the two next bits and the opposite could also be true so for example we could have a number here which has let's say four zeros that tells us that our X number should have zero bits that are set and to make it more interesting I guess I could say a one bit set in which case we know that our output has to have one bit set we want it to be as similar to this as possible so what do we do do we make our number to be 0 0 01 or do we make it to be 0 0 1 0 we definitely want to pick either this B or this bit well which of these is going to result in a minimal xor well once again we can consider our starting point to be N1 itself so we have this number 0 1 1 but we only want one bit to be set so we have to unset a bit from this number here but which bit do we choose well we should choose the least significant bit once again before we were adding a bit now we are removing a bit but once again we are going to to do the least significant bit because by uh changing this bit we are making it different from what the original number was which was 0 011 and basically we're going to set that bit in the output when you actually exor the numbers now cuz now that they're different here this is going to be a one in that spot whereas it would have been a zero before these things are not too difficult to handle in terms of code as long as you know kind of the main bit shift operations I think the rest I can probably cover in the code so let's jump into that so the first thing I'm actually going to do is Implement a helper function which is going to count the number of bits given some integer n which I believe is actually its own leak code problem I think that's a leak code easy and yeah I think if you go to my NE code 150 list it actually is one of the fundamental uh bit manipulation problems so if you're a beginner to bit manipulation I definitely recommend checking out these problems counting bits here is a very good one and that's basically what I'm going to be implementing right now or at least an easier version of it so first let me actually show you how this is going to be used we want to count the number of bits for Num one and also for Num two because based on that is how we're going to implement the rest of this function so that will give us some variables which I want to call count one and count two so this function here I'm going to have result which is going to be the number of bits that's what we're going to return and then we can say while the number is great greater than zero we want to get the bit and then we want to take the number and then shift it to the right by one so what this is doing imagine if I have a number like this I want to get this bit and then this line here is just going to take everything here and then shift it to the right so pretty much like removing that last digit now in order to get this bit here we can just uh do the bitwise and with the number one this will basically give us a zero for everything in the output for all these spots but this one will be compared here if they're both one we'll get a one in the output otherwise we'll get a zero that tells us what this bit is so we can do one anded with n and so the result of this is what we want to add to this this will either be one or zero so that will tell us if the bit was one or zero so now that we've implemented this part I'm going to have two different Loops down here which I'm going to combine but I don't think the combin finding is really the important part so we're going to start with a number X I'm going to make my starting point to be the first number one CU we want it to be similar to this number and so X is what we're going to end up returning so first I'm going to have a loop one is where we are removing the least significant uh bits and then the other is where we're adding uh the least significant bits so we would be removing if the count one was bigger than then count two we have extra bits in Num one which is what our starting point is so we want to remove from that so we only want to remove the least significant bits that are actually set so how do we know if a bit is set well we look at X so with that it kind of works similar to what we have here but we are going to do well I guess we're going to keep track of which position we're at so I'm going to have I to do that so I have my ey pointer which is zero right now so that's the bit that we're going to look at so on each iteration of this loop we're going to increment I by one so to check we're going to say this one shifted to the left by I so anded with the number X this tells us that the bit is set so this will evaluate to true if the I bit is set in X in which case we would um decrement the count of one that tells us how many bits are set in the first number and then if we're removing one we can decrement that but also we want to UNT ble the bit in X and that's the more important part so here x how uh can we unset a bit setting a bit is as easy as anding well unsetting it can be done with the exclusive or we take the number itself and then exclusive or it with uh one shifted to the left by I because either that position will already be set which will make it a one which will mean we are unsetting the bit one exord with one is zero otherwise it's not set and that isn't really possible cuz we already verified that it actually is set with this condition now the good thing is that adding least significant bits is pretty similar so I'm actually just going to copy and paste this and flip the condition around because now count two should be greater so we are adding significant bits so we will be incrementing the count and so here if the bit is set is not what we're looking for we're actually looking for unset bits so if this is actually equal to zero so if the bit is not set then we want to set that bit so here instead of doing exor we can actually do the or operator so this is actually the entire code let me run it just to make sure it works and yes here on the left you can see that it does and I might as well combine this Loop because it's easy enough so the trivial way to do it is just to check that these are unequal and then you can move one of the conditions into the other but I think even the condition themselves are kind of dependent so what I'm going to do is add uh the condition here if count one is less than Count 2 and that's the case and the other one is the opposite where Count 2 is bigger than count one so that's kind of a very minor change I don't think it's really necessary there's probably other ways to clean this up as well um but in terms of time complexity it mainly comes from the fact that we're counting the bits so that is going to be proportional to log base 2 of whatever n is num one and num two I assume they're 32-bit integers so technically this should be constant but if they were arbitrarily large this is what the time complexity would be if you found this helpful check out n code. for a lot more thanks for watching and I'll see you soon