Neighboring Bitwise XOR - Leetcode 2683 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem neighboring bitwise xor and honestly I really like this problem it's pretty original and it just kind of feels like solving a little like math puzzle so the idea is that we are given a binary string so it could be something like this 1 1 zero and it's actually given in the form of an array so not a string but a binary array so here's a couple examples and the premise of the problem is that this array is the derived array the array that we're given but the array itself was actually made from another binary array so for example I think this one could have been formed with 0 1 0 the reason for that is each of these values so this value itself it represents the exor of these two elements this element and the element exactly to the right of it so 0 and one exord is going to be one so we would put a one here and then 1 and zero exord together is also going to be one so we put a one here now for this last element it doesn't have a number to the right of it so we will kind of loop back around assuming it's like a circular array and then get the xor of these two since they're the same number the xor of them is going to be zero so that's what we get in the derived array remember this is the array that we're given and this is the array that it was derived from our goal is not to recreate this in fact I don't think it's possible to recreate it because there's always going to be at least two solutions or possibly no Solutions which is uh what the problem is getting into but for this example here you can see that if we were to take this and invert it do the opposite of it 1 0 one it would also satisfy the derived array because just based on the definition of exclusive or if we have a one it just means that the two values were the same or rather sorry if there's a one it tells us the two values were different it doesn't tell us anything about the values themselves it could be either 0 1 or it could have been 1 Z and the same is true for all the other ones so this one would tell us that these two are different now depending on what we picked for the first element if it was Zero then the next one has to be a one and then the next one would have to be a zero or if we had started with a one it could have been the opposite they could have still been different this way honestly I think when you kind of realize that if you're able to make that observation and it's not something you would necessarily be looking for but when it comes to these types of problems the main thing you want to be doing is trying to make some observations trying to look for some hints or some Clues on how you can try to like simplify the problem and so now I can finally get into what the question is asking the question is asking is it possible for us given the derived array to create the original one we don't actually have to create it but is it possible for one to have existed that would have been able to create this array given like that exor rule so at first you might think well what could a counter example possibly be because when you think about it in that like these two elements will decide this one and then the next two elements will decide this one so what would make it impossible for example if we had a derived array of just a bunch of ones that tells us that the original array must have had differing bits for these two spots so maybe a zero and a one well then this tells us they must have been different here as well so maybe one and zero and so to recreate something like this you would just create like an alternating array given a derived array of a bunch of zeros and I think that would tell us that all of the spots like these two would have to have been the same so maybe all ones or even all zeros I think would work because each of these tells us that these two are the same same this tells us these two are the same etc etc again I'm just like making some observations I think this is kind of an important step if you have no idea how to solve the problem just start to kind of think of some examples think of what they would look like maybe there's some patterns or maybe there's not well anyways they give us this example down here which is a very good example where it's actually not possible to create the original array because this one tells us that these two numbers in the original array must have been different if we got a one here so either this was zero and this is one or this is one and this is zero this zero tells us that this number and the number after it so now we're looping around these two numbers they must be the same so obviously that's a contradiction like that just cannot be possible so in this example we have to return false is this the only example where something like that would happen happen no and in fact the reason that this can happen in the first place is because we are sort of looping around if it wasn't for looping around then I don't think it would actually be possible and some very brief uh intuition of why that is I don't know if this will be more helpful or maybe more confusing for some of you guys but off the top of my head uh one way you could think about it is like this where these two numbers will decide what goes here they don't necessarily decide it but they will kind of influence it like either this will be a zero or a one and whatever we decide for that like this is X then the following rules and I kind of have it backwards it's these two that are deciding that so this zero would tell us that these are both going to be the same but either way like if we were just going from left to right and this did not influence the one that comes around then we would just stop eventually we'd have a kind of a chain where like if this is X then that'll tell me that this is also going to be X or this will be the opposite of X and some kind of sequence like that but eventually it Loops back around eventually you'll have something at the end of here that will say that this actually should have been the opposite of X it should have been a zero or it should have been a one when it was the opposite and so that's where you get like the conflict almost like cycle detection in a way but in terms of how we can use this information to actually like solve the problem it's not as bad as you would think I'm going to implement this I guess in what I would call a brute force or simulation way I think it's a relatively approachable way to solve this problem I think there are a few other solutions that I didn't really look at Super closely but the one I'm going to show you is going to be of linear time and constant space and I think conceptually it's pretty simple like I'll give you the intuition of how I came up with it so it kind of gets back to that point of looking for like a contradiction as well as knowing that this one just tells us that the first two bits are going to be different it doesn't tell us what those bits are whether it's a zero or a one so how do we run the simulation if we don't know what to do are we going to make a decision tree and have two different possibilities at every single step no that would be inefficient and we also can recognize that just kind of based on like symmetry I don't know the formal way of putting this but just in terms of like if I gave you a string that said 0 1 011 and then I invert this string and I give you 1 0 1 0 0 I mean what exactly is the difference between these couldn't you just say it's sort of like a reflection or like an inversion of the other and kind of the way that exor works as well if you have 0 xord with zero that's not any different than one exord with one same thing zero and one and one and zero these are the same as these and so kind of just based on that I know that I can put either a zero or a one in the first spot it does not matter as long as I can decide that the rest of this should let me fill in the rest of the string and then eventually I can loop back around and if there's a contradiction then I return false otherwise I will return true the reason I mentioned this stuff as like the intuition is because I don't always necessarily do all of this in my head before I start to implement the code sometimes I even notice things in the drawing explanation that I didn't when I was coding this up and that's why I call it the intuition because it's just to lead you towards what the correct solution actually is but actually implementing the correct solution might be different from how you came up with the solution so anyways knowing that what I'm going to do is this I'm just going to arbitrarily put a zero in the first spot so now I'm going to go through every value in the given array the derived array and so this one tells me that these two values are going to be different since I decided to put a zero here for the next value that I'm going to fill in here I'm just going to do the opposite of the previous one one so that's going to be a one this time so notice by visiting this value we populated this guy and so this since it's a one it tells us that these two are different and so I'm going to put the opposite of what I had here so I'm putting a zero here and then lastly we get here which should tell us which value is going to go here in the first position and since it's a zero that tells us that uh this and the previous value should be the same and right now they are so we are good now if I were to change the example a bit if I extend this a bit if I put a one here and maybe a zero here so this told us that there should have been a zero here because these two must be the same so now I have a one here that tells me these two should be different so I'm going to put a one here and now with this zero it tells me that this and this should be the same but they are not the same thus we have to return false so we won't know until the actual very end if we have a contradiction or not but the way how I'm going to implement this in terms of code is we know that for the first value we are going to pick zero no matter what so that's what I'm going to call the first value then I'm going to have what I call the last which is going to be the previous value I guess initially it'll also be zero and then we will use this to fill in this part of the array until we get back to the beginning and so at the end we can check if these two are equal then we return true if they're not equal that means we had a contradiction in which case we returned false so now let's code it up okay so coding it up I'm going to have that first variable I just mentioned as well as the last variable and then at the end we are literally just going to return if first is equal to last this is going to be pretty quick so I guess I'll go slow just to really explain everything we are going to go through every number in the derived array we know that each number will tell us something about the pairs in the original array we already have the first value in the original array and so if this is a one then we will flip it we will set last equal to the opposite of what it happened to be otherwise we will keep last to be the same so obviously we can clean this code up by just getting rid of that and then change this to just ifn is truthy and I think this is pretty much the whole code I don't remember if python actually supports this or not but let me go ahead and run it so yeah it looks like it does and so this works it's pretty efficient there's not really much to explain I guess of like what's going on here I think the whole like cycle detection thing that I was talking about how it like Loops back around is probably the most important part as well as the fact that we can start with either a zero or a one I know I didn't give like a formal proof of why this is correct but I think intuitively it makes a lot of sense once you think about it but I don't really have a form proof so sorry if that's what you were looking for maybe somebody can provide their reasoning like in the comments or something but if you found this helpful check out NCO doio for a lot more thanks for watching and I'll see you soon