So, I really do want to uh look at this article. It's called the XOR trick. A, it's not AI, so it makes everybody happy, but B, it makes me happy. I know that no one's going to actually watch this video, but for me, I actually makes me really happy. For those that don't know, there's like a lot of cool things you can do with Exor. So, even before reading this article, the reason why I wanted to read it is that I just love the idea of Exor because XOR is just such a fun thing. It's one of the few operations that has memory built into it. So, look at this. So if I go like this 1 0 1 0 and then I go say 0 1 1 0. If you exor those two values together meaning that exor means exclusive or meaning if one of them is true then the statement is true. If both are true or both are false it's not true. So this would be not true not true. Then we exor this again. Right? So I'll go like this. We exor this again. Uh, this would be 0 1 0 1. And then we can exor this bad boy one last time. 1 1 0 1. Uh, wait. 1 one zero. Wait. 1 0 0. What do we get? We get 0 or we get 0 1 1 0. Now, if I go like this, a equ= b equals a equals b still equals the same thing. Then I go like this. B equals this. A equals this and then I throw in A now equals this. You'll notice that the value of A which is 0 1 1 0 and the value of B which is uh here I'm going to write down here 0 1 0. I swapped the value of A and D. And so I love Exor. I think Exor is super cool. And I'm sure there's other tricks I don't even know about when it comes to Exor because you can do all sorts of really cool things when it comes to Exor. It's like it's so neat. So let's look at this. Uh there's a whole bunch of popular interview questions that can be solved in one of two ways. Either using common data structures and algorithms in a sensible manner or by using some properties of exor in a seemingly hard to understand way. Oh my gosh, I'm already so excited. This is so exciting. Well, it seems unreasonable to expect uh because one time uh I wrote uh what's it called? I tried to write in 20 minutes and see a linked list that only uses exor. Almost got there in 20 minutes. It took like 22 minutes. But you can do you can write a linked list a doubly linked list using just exor. You can exor inmemory. You can exor links. You can change you can do all sorts of fun stuff. What are the pract practical use cases uh to make whiteboard interviewers feel dumb. Okay, that's the goal. You go into a whiteboard interview and they're like, "Hey, do hey, why don't you do this doubly linked list?" And you're like, "I got that. I don't Hey, I got you a doubly linked list." And then you use a but then you just throw in uh a equals a x or b. Uh b equals uh a x or b. Uh a uh a equals a x or b. And boom, you have yourself two swapped pointers. Oh my gosh. They're going to be like, "What?" And you're like, "Yeah, I linked this. What are you talking about?" Oh, I didn't realize this job you created temporary memory. Yeah, right. You gross. Okay. This is caveman logic prime. Of course it is. I'm a caveman. Okay. I've bar I'm still in South Dakota. You didn't know this? I'm supposed to work here and you don't know basic logic. While it seems unreasonable to expect the exor solution in interviews, it is quite fun to figure out how they work. As it turns out, they are all based on the same fundamental trick we will derive at uh in a bottomup way in the in this post. Afterwards, we'll look at a bunch of applications that use XOR tricks such as solving the popular interview question. You are given an array of x of n minus one integers which are in a range between 1 and n. All numbers appear exactly once uh except under uh except one number which is missing. Find this missing number. Wait, hold on. Oh, interesting. How would you do that? Okay, so this must be in my immediately in my head I think of this must be unevil uneven level protection, right? You could probably do ulp fec. This is probably a variant of ul uh fec. Oh my gosh, I want to know about this. Of course, there are a number of straightforward ways to solve this problem, but there are also, let's see, but there is also a perhaps surprisingly a surprising one. You using exor. Oh my gosh, I can't read. Hey everybody, I had a stroke. Hey everybody, I had a stroke. Hi, I had a stroke. Unstroking. Um, all right. Exor is a logical operator that works on bits. Let's denote uh it by this thing. My first thought of using exor here. Honestly, I honestly have no idea how to do this other than I have no idea how you would do this with exor other than doing this. You have a uint 8 array, right? You have an uh or yeah, you could just use uint array, right? And inside of your 8 array, you take whatever number you find, right? Which is you know this number is somewhere between one uh one to n, right? So you know x is somewhere in there and you go literally x uh the floor of x / 8 just for you JavaScript kitties, you know, just in case you forget that when you divide it should be an integer should be a float. I'm kidding. I actually really love the fact that in dynamic languages you don't have to do stupid number conversion. You do one of these ones. Okay, so this is where it appears in here. And then you could do a fun little mod 8, right, to know what bit you're flipping. And then you could do a little one over over uh xod 8 uh x mod 8 minus one, right? x mod 8 minus one. You could do that and then flip all your bits and then walk through this int. Then walk through this array until you hit the first zero. Like you could do that. That would be a way. But I feel like that's crappy. Uh sneaky insert. Uh they ate there. Thank you. It was a very sneaky exor int range. Then xor the array then diff. See, I'm not sure. Hold on. on uh exor is a logical operator that works on bits. Let's denote uh it by this. If two bits uh see I feel I feel like this is an unevalable level protection, right? That's what it's called. It's a it's a RTMP uh correction algorithm. I bet you it's going to be awesome. If two bits it takes in the input are the same, the result is zero. Otherwise, it is one. This implements an exclusive or operation. Hence, exor. Uh exactly one argument has to be one for the final results to be one. We can show this with the truth table. Bam. Most programming languages implement uh carrot as a bitwise operator, meaning exor is individually applied to each bit in the string of bits. There we go. Bam. Bam. Bam. Bam. There we go. So, we can do this bad boy right here. Because of this, we can apply exor to anything, not just booleans. All right. It'd be weird to do it to booleans. I only know exor on non boolean stuff. Deducing some useful properties. We can derive a bunch of properties from the previous definition. Let's go through them one by one and then compose them to solve the interview question previously mentioned. Exor and zero. Exor 0 equals x. Yes, this is the base argument. In fact, if I am not mistaken, I feel like this is like the first ax. This is like the first thing you learn in hacker's delight. I I feel like I need to reread this. Yeah. So, the first thing you do is manipulating the rightmost bit, which is x and xus one, which is, by the way, fantastic move. This is so good. This is such a cool This is such a cool little trick. Even this little bad boy right there. Super super cool. Hacker's delight. I love that one. It's actually useful in practice. Yeah. Yeah. X and Xus one is like actually a super useful thing. Let's see. Exor on the same uh argument is zero. That makes sense. That's why if you have you once once you do the same value twice, it sets everything to zero and screws everything up. That's the one weakness of exor. Uh intuitively this means that if we apply exor to the same arguments they cancel each other out. Uh commutatively exor this one commutatively uh communivity uh exor is commutative uh meaning that we can change the order and it's still the same thing. That makes perfect sense. You can just see that by the way it is. It's you can tell it's a yellow aspen by the way it is. Uh you can see that this and this end up being the same values. The sequence of exor operations. By combining all of this we can uh deduce the central insight behind everything that is about to follow the exor trick. If we have a sequent of exor operations a b c then we can remove all pairs of duplicate values without affecting the result. Okay. So this is this is really looking like uh uh forward error correcting. Okay. So I'm so curious how they do this communively commutatively allows us to reorder the applications of exors so that the duplicate duplicated elements are next to each other. X or XR equals Z. A X or this equals A. Uh, each pair of duplicated values has no effect on the outcome. True. Oh my gosh. Hold on. Okay, hold on. Hold on. Hold on. Hold on. Hold on. Hold on. Hold on. Okay, hold on. I I can't be right. It can't be right. So, let me just try this. Okay. Uh, here. Let me just try this. Let me just try this uh on. Sorry. I just have to try this now. I just have to try this cuz this seems like really, really cool. Um, I'm just going to go like this. Do I have a little test file? No, I don't. So, I must be misunderstanding this. Honestly, I have to be misunderstanding this. I just have to be. So, here we go. Let's go like this. Um, let's go like this. Uh, function uh test uh r, uh, yes, it's a number array. There you go. Thank you. Uh, let's see. Uh, let let sum equals zero for let i. Yep. Thank you. Uh, here, I'll just use that for now, but we're going to change it to exor, right? Uh, return sum. Okay, cool. Right, we're going to have this little bad boy right here. So, I have this nice little I I wanted to test this out. Okay, so this is this is my theory const uh result one is going to be test 1 through 345. Result two is let's remove a three. Now, that means we have removed uh 0 B 01 1 0, right? That's three. Wait, no, that's not three. What the hell am I saying? That's four or six. Uh it should it that's the value that's not present. So that means if I go console.log res two have I is the only thing remaining zero or I mean three dude no way. That's crazy if that works out. There's no way that's true. I refuse to believe that. Here I'm going to remove that just so I can use node to run this file. Uh I have bun I think. Oh dear sweetness. That is so awesome. That's cool. That is so cool. Oh my gosh, math. Not even once, bro. Not even once. Explain it again. Okay. Okay. So, when you when you exor a bunch of things, remember exor has memory. So, what was the rule to this exor? It's actually really really clever. Holy cow. It's so clever. What is What is a xor zero? What does that equal? That equals a. What does a xor a equals? Zero. sorting does not matter. No, it remember that's the communive law uh law which is uh x x or y equals y x or uh x, right? That was the other rule, right? So that was rule number one. That was one rule we looked at. And then we also looked at this rule right here. That means that 1 xor 2 xor up to n minus one effectively contains the combination the combination of all of these put together. So now if I have 1 x or 2 all the way up to n minus one except for one missing variable, right? One missing variable or one missing number. That means when I exor all these together, what's going to happen? Well, what's going to happen is that it's going to be this. Remember in these two lists, we're going to have one x1. What's the value of that? Zero. We're going to have two x or2. What's the value of that? zero. We're going to have uh we're going to have four x or four. What's the value of that? Zero. What is going to be five x or uh five? It's going to be zero. What is the remaining three that we have? It's literally going to be three. Oh my gosh. It's because everything appears once. I did not know that. So, you're just dipping the list with a complete set. Yeah. Yeah. Yeah. Yeah. Yeah. Yeah. Yeah. Yeah. Yeah. Yeah. Yeah. Yeah. Yeah. Super cool. Very cool. I did not know that you could do this. That just this just blew my mind. So just once I read this, I realized like, holy cow, that was Dude, I love that. Oh my goodness. And it works if N1 my values aren't sorted. Exactly. I was just I was just doing that by lining everything up. Oh, it makes so much sense. Yeah, because look, he he does it right here, right? Because if you take two lists with the same values in it, you actually get a a you get b and then you only have a c remaining, which is the same thing as this, which is the same thing as that. All right? Because uh exor is bitwise operated. It will work regardless of what kind of values a and b and c are. This is uh this idea is really at the heart of how exor can be used uh seemingly magic in many situations. So, this is actually how Ford error correction works. I can't believe I didn't see this. This is literally Ford error correction. That's why I called this out. So how Ford error correction works, if you're ever uh curious about it, look up ulp uh FEC uh exor, right? And so this one right here, this is just like a Ford error correction that's pretty dang cool that uses a simple exor to be able to do correction right here. And so it what it does is it effectively you can take a series of frames, a series of packets, exor them all together and you can send down a singular packet that is the exoring of all those other packets. That way if one packet is missing you can effectively recover that packet by exoring everything together you'll get the final packet back out. And so it's called an un you know so you can do it to certain levels of your media to be able to protect it. when I was doing I actually had to write a test and write a harness to be able to test this inside of Netflix's gaming stuff which I'm shocked that I did not know. I'm such an idiot that I could not solve that. Dude, can't believe I didn't even know that. Dude, XRdev, how great is it that you do shader stuff. You're you're you're a dev and then you just ran into all this randomly. Hey, if you ever do stream, due to the serendipity of this situation, if you do stream, I will raid your stream. you just as long as you can do it during a time that I am doing. What if you're missing two packets? Then you can't recover it. But if you do two packets of FEC, then you can recover it. Ah, this is so funny. What a funny day. All right. Application one, swap in place. Um, before we solve a problem of finding uh the missing number, let's start with a simpler problem. Swap two values with x and y in place. I already just showed this, right? XYX. There you go. You can do that. That seems a bit mysterious. It's actually makes perfect sense. uh because Oh, nice. I like the diagram that they have, which is going to be uh this right here. That's fantastic. So, we've already seen this. So, we already understand this thing. I wanted to offer FC. Oh, well, thank you. Um so, FEC uh basically doubles memory cost. It doesn't double memory cost because you only send down one packet. Let's just say that uh when you're sending down real-time video, if you're sending down real-time video and this one frame has uh say three packets of UDP that need to come down, you can send down additionally a singular packet of FEC. You'll notice that if you do a SDP, which we learned about SDP when Facebook was monitoring everybody's traffic, remember when we talked about SDP, stream description protocol. Remember that? Remember that? Remember that fun times? uh when when Facebook was taking advantage of uh the Android operating system, SDP, stream description protocol, will have things that actually tell you about how this stuff works. And one of them, I think, is something like it looks like video. It's like video fck, right? And what this means is that you have a channel that's the video for error correction layer and then you have this one. So that way if this thing is missing all you have to do is if this is a this is b and this is c and this is the fck of this packet we'll call this fck zero. If you just do uh a xor uh c xor f0, this would be the equivalent of doing a x or c x or uh x or a oh my gosh x or b I'm running into my keyboard x or c which remember c and c that makes zero. A and a that makes zero. So what is left? B zero fcks given. You should have at least one fck given. Okay, brothers, we need one fck given if we're going to do this. Ah, love this. The fundamental insight here is that having x uh x or y uh xx or y uh in one register and let's see and x in the other allows us to perfectly construct y. Once x uh xx or y is stored instruction one, we can uh just put x in the other register instruction two and then uh and then use it to change xx or y to y. Application finding the missing number. Let's solve this problem uh posed. By the way, we already know the answer to this post. I just want to read through the article because I think I I'm just super stoked about the article. I want to see if there's any other insights. I don't know because this was awesome. I'm like super stoked about this. I absolutely love this. I like just did this makes me super happy. Let's find let's see. Let's finally solve the problem posed at the beginning of this article. Give it an array of this one. Uh let's see. All numbers appear exactly once except one number which is missing. Find the missing number. Of course, there are many straightforward ways of solving this. I just I mean my default mode would be just use a map, right? I think that's everyone's default mode is just use a map because that's easy, right? Um but we uh but we set out uh to do it using XR. Someone's asking what's the runtime of this? Obviously the runtime of of this algorithm would be uh 2N, right? It's just 2N, which is fantastic. So that's pretty good, right? 2N with uh nothing else. Yeah. A map, a set, they're the same thing. Okay. A a set is just a special case of a map, right? You're still doing hash lookups, right? Theoretically hash lookups. Let's see. Of course, um there are many straightforward ways of solving this, but I did say, let's see, sorry, someone distracted me with a very large message that was just Stormmy Daniels, shut up. Um from the exor trick, we know that having a sequence of exor statements mean we can remove all duplicate arguments if we just exor all the values in the given list. However, we cannot apply this trick because there are no duplicates. Right, there we go. Note that a minus 2 is the last index of this many elements. We can additionally uh let's see we can do additionally uh is to also exor all the values between one and n. True. This will give us a sequence of exor statements where elements appear as follows. All values in a given list now appear twice. Once from taking all the values once because they are in the original list. The missing a value appears exactly once. Once taking all the values between one to n. There we go. So this is literally so I did call this at the beginning. This is literally forward error correction. I thought it would be forward error correction. Holy cow, that's super cool. There you go. They're just going to do that one. Um, generalizing this beyond integers. Okay, I want to see this. While working with integers a one to n. Uh, so far this is not required. In fact, the previous algorithm works in any situation where there is some set of potential elements and two a set of elements actually appearing. The set may only differ in one missing element. This work this worked out nicely for integers because the set of potential elements just corresponds uh to the elements from one to n. One could imagine applications where elements are not integers one to n. A set of potential elements are person objects and we ought to find one person missing from the list of values. Oh, we have a missing person's report. I would have gone with media. This is really where media takes place. This we're watching Twitch. What do you think Twitch is doing on the back end? We're exoring. They could be read soling but they probably are exoring. Uh the set of potential elements are uh are all nodes in a graph and we're looking at a missing node. Uh the set of potential elements are integers in general not necessarily from one to n and we want to find the missing integer arithmet arithmetic operators instead of exor. If the algorithm uh still seems a bit magical uh in which let's see which I hope it does not it might help to think about one could achieve the same result using uh arithmetic operators. Oh yeah, you could probably just add them all together, right? Yeah, you could just add them all together and subtract them all out and boom, you got it. Okay, that makes sense. Yeah, that's cool. Yo, bro, that's like that. Hey. Yeah. Hey, bro. That's really cool. You could do this with one loop, couldn't you? Well, wait a second. Wait a second. If you find missing, you could do this with only one loop. Okay, since we're here and we're going to try to make this faster, let's make it faster. Okay. So, if you're given an array and you're given the n, that means what I could really do is I could do the following. I could actually just add this and I could just minus that or minus uh that. And there you go. That would be the missing ones. Look at that. I did it with one loop, bros. We just solved the universe. Um, right. And then we just have to go like this. Uh, sum minus equals um minus equals n minus one. Right? Boom. One loop is not faster because it can be simed. Hey brother, we're talking about Big O. Big O doesn't care about your real world. Okay. Big O doesn't care about your real world. Big O is all about showing that you're smarter by saying that you use less N. Okay. I use way less N than you, loser. Uh, two loops have different uh number of iterations. Again, you're wrong. In Big O, that's not true. Okay, Big O, that's not true either. They both have the same number of iterations. Okay? Because in big O, N minus one equals N. Now, obviously, I did 2 N, which actually is just N also. This is true also. So, they're actually the same answer. We both got n. But then I can casually flex on them with, oh, you did 2 N. I just did N. So like even though we do bound to the same upper bound, I only did it in n loser. Skip the answer. Smart. Thank you. All right. Anyways, let's keep on going. Uh here we go. The solution is not uh as nice because it would need to handle overflows because they require some types. Uh yeah, that's why you did the minus at the same time. If you do the minus at the same time, I believe that would avoid the uh the exact problem you're talking about. Potentially. Maybe not. I guess if you had a bunch of if you did technically do it from two to the 32 and you had an inversely sorted array list, you'd overflow. Yeah. Okay, fair. I'll accept it. Fair, fair, fair, fair, fair. Uh because it requires a type of elements to support with plus and minus with certain properties. It it however has the same logic of elements canceling each other out because they appear in a certain number of times. Yes. Uh application finding duplicate number. Here's where it gets fun. We can apply the exact same solution to a similar interview question. You are given an array of n plus one integers which are in the range between 1 to n. All numbers appear exactly once except one number which has uh which is duplicated. Find its duplicated number. Oh, okay. Hold on. Yeah, you do the exact same thing twice, right? Yeah, you just you had to exor it twice and boom, you're the exact same solution. Yeah, I just wanted to think through that just to make sure it was the exact same solution. All right. Anyways, the duplicated value appears three times, right? That's right. There you go. That's why that's why it works. Exactly. Because it appears three times. Let's see. As previously, all the duplicated elements cancel each other out. This means we are left with exactly what we are looking for. The elements uh that was duplicated in the original array. The element appearing three times combined with X or reduces to the same element. Right? There we go. Bada bing, bada boom. All okay, this is awesome. Okay, what's this one? Finding two missing duplicated numbers. It turns out you can take this even further. Consider the following slightly more difficult problem. You are giving an uh an of n minus two integers which are in the range of 1 to n. All numbers appear exactly once except for two numbers. So, I forget how to do this, but I know that you need two forward correcting bits to be able to do this. Uh, as before, the problem is completely equivalent when looking for two duplicated numbers uh instead of two missing numbers. I'm pretty sure you could just I'm curious how they do this. I'm sure you've guessed it, but we'll stick uh with what worked before and start exactly the same way. I actually can't think of how you'd solve this off the top of my head. I How do you decode the packets? I know you need two You need two packets. Anyways, here we go. I'm sure you've guessed it, but we'll stick uh to with what worked before and start the exact same way. Let's consider what happens if we use the previous X or algorithm. It won't work because you have two missing numbers. So, you can't actually determine what what it is, right? If we do that again, we end up with a sequent of X or statements where all elements cancel each other out except for two that we're looking for. We'll denote this by U and V. Mostly because we have not used those letters before. After applying the previous algorithm, we are left with just U X or V. Uh what can we do with that? Somehow, we need to extract U and V from this value. But, uh but it is not immediately clear what to do. Correct. Partition based on inspecting U and V. Luckily, we can figure out what to do by using what we've already started earlier. Let's think about this. If two bits X or takes as input, let's see, are the same, the result is zero. Otherwise, it is one. True. Okay. If we analysis uh analyze the individual bits in UV, then every zero means that the bit uh the bit had the same value in both U and V. Okay. Okay. That means every one is that the bits different. Okay. Okay. Okay. Okay. Okay. I see. I see where this is going. Yes. Yes. Yes. Yes. Uh using this uh go for it. Uh exordev, go for it. I'll I'll see if you are streaming after this. Uh using this uh we find uh the first one in U V the first positioned I where uh U and V have to differ. Then we partition A as well as the numbers from one according let's see one to N according to that bit. We end up with two partitions each of which contain two sets. Partition zero the set of values from zero to uh one to n where the e bits is zero. The set of values from a where the e bits is zero. So hold on hold on. Okay. So what they're saying is let's pretend that uh we know our little fact that let's pretend we're summing up the numbers uh zero through eight. Okay. And let's pretend uh that u is six. that's missing, right? And V is three. That's missing, right? Okay, let's pretend let's pretend that's it. That means our value that's coming out is going to be uh u uv, right? Which is going to be 01 uh 01, right? And so what we're saying is we're going to build a partition based off the first one right here, the leftmost one. I believe I got that correct. which means that we'll have a partition that is going to be numbers that are starting at this high value and numbers that's everything else. That means we're going to have two effectively forward error correction packets that are going to look something like this that we'll have what is that? That's uh one two four. So we're going to have four and higher. So that'd be four through seven on this side, right? That would be this side. And then we're going to have uh uh three through zero on this side, right? Or I guess it's technically three through one, right? And that's our two partitions in which we should be able to sus everything out with that. Right? So I I feel like this am I understanding the partitioning correct? Right. Partition zero. The set of all values from one to n where the e bit is zero. The set of all values. Oh, is hold on. Let's see. Hold on. Using this we uh let's see. We find the first one in UV in the first. Oh, okay. So, it's the rightmost. Oh, so we actually do the rightmost, right? We're doing the right. Is that what we're doing? We're doing the rightmost bit because if we're doing the rightmost bit, we can do the the old trick of right of of x and uh x. Oh my gosh. Minus one, right? I'm pretty sure we can do that, right? So, I'm pretty sure you can just do that to get the rightmost bit. It's the left uh the least significant bit. Yeah, I think it's the least significant bit. That's what he means by doing it this way. Okay. Okay. Since U and V are diff different in position I, we know that they have to be different uh different in different partitions. True. Reducing the problem. Next, you can use another insight described earlier. While we worked on uh integers from one to n so far this is not required. In fact, the previous algorithm works in any situation where there is one some set of potential elements and two a set of elements actually appearing. The set may differ uh in the one missing or duplicated elements. All right, these two sets correspond exactly to the uh sets we have in each partition. We can thus search for U by applying this idea to one of the partitions and finding the missing element and then find V by applying it to the other partition. Uh this is actually a pretty nice way of solving it. We have effectively reduced this uh this new problem to a more generalized version of the problem we served uh uh solved earlier. I'd love to see some code for that cuz I feel like I still don't quite understand how that works, right? What am I missing here? It has to be the leftmost bit, right? It it No, it has to be the It has to be the most significant bit. It has to be the most significant bit. I understand why it has to be that, right? because the least significant bit in this case would be uh one which means you'd have the list of one and then you'd have the other list of effectively uh seven uh of seven through two right and both U and V appear in seven through two but if you take the most significant bit and give it to me all you always get the answer of one and the other right because that's the first place they differ in the most significant so therefore That's where one of them has a bit set to one and the other one doesn't. So, it actually has to be that, right? I think I'm correct on that one. Okay. So, how does this work here? Let me let me just try to make this work. You and V cannot be the same. Well, no, because then there's only one missing number, right? You you see you see what happens. When there's only one missing number, then there's only one missing number. Okay, so let's try this. All right, we'll we'll keep on going with the same example, right? So, we have U and B right here. Okay. So that means we have uh the following list. We have uh the example list would be uh 67. Right? Right. That's 1 through 7. Right? Is that that's that's what we're doing. Right. We worked with integers from 1 to n so far. What what's the exact problem? Let's I just want to understand this because I actually just want to understand this article. This is all right. You're given an array of n minus two integers which are in the range between 1 and n. Okay. So we'll go up to eight. There we go. So there we We have between 1 and 8. That's our example array. So that would be the full one. In our case, we are our our missing is going to be 1, two, not three, four, five, not six, seven, and eight. Right? So that means our um our let's see our let's see our result will will be simply test example exor test missing. Right? So that's like our resulting one. So this represents uh UX or V, right? Okay. So you can see that right there. We have that bad boy right there. So now what we're saying is that we need to walk through this and find the first most significant bit and then we have to create that as two subarrays. Right? We have to create that as two subarrays which would be four, not five. Four. Right? Right. So that means um uh here function uh uh most significant bit. I don't know I don't actually know how to find the most significant bit as an algorithm. I I don't know if there's like a bit trick to find the most significant one. Is there a bit trick to find the most significant one? Yeah, you have to keep shifting until it's zero. Right. Is there any other way to do that other than that? Right. So I go like this. Uh most significant uh bit equals um zero. Right. And so I go like this. While n is greater than one, we go like that, right? Wait, is that true? Hold on, hold on, hold on, hold on, hold on. While n is greater than zero. No, we just simply go like this. We're looking for the most significant bit, right? That was a little bit wrong. I have no idea how that works, but I'm glad to give that a try. I have no idea how that works. I'd have to think about that, but let's find out. Uh, looks like this. Const u equals We know for a fact that const u is three. We know that v is six. So you're saying that uh u v um you're saying uh x or that or and that together and that together by the minus of u and uh v is one. So that that right there is not it. That would be the um what's it called? That's the least significant bit that they have difference. It's the most significant bit. Oh not minus till day. Just in case there's some sort of that should be zero. It can't be tildy. Of course that's zero because this is literally all the zeros are ones and all the ones are zero in this one and then we and them together which makes all the it would literally be all ones and zeros on opposite side. It's like perfectly negating it out. Yeah, I did that wrong. Yeah, it's okay. It's okay. A lot of like dude I I get these I get these pe you know this is not this is not most people's strong suit. Okay, this is not most people's strong suit because it is uh you know none of us do this for like unless if back when I was doing things in uh robotics and all I did hey we did find zero then yes I was much stronger at that but I haven't done this in so long even when I was doing uh network algorithms I still don't it's not like you do this a lot you actually do this you actually do this very little okay so if I've done this correctly I'm just going to pretend I think I'm going to pretend like this does find the most significant bit so here just go like this uh let's go like this console console. Uh here output console.log result and console.log most significant bit result. Let's just see if I got this right. Right. Oh my gosh, I just killed my 11 streamer. Don't do that. Uh no test uh js ts. There we go. All right. So that did technically do. Did that do that? The most significant bit is three. The third bit is the one. Yeah. Would Yes, that should be the most significant bit is the third bit. All right. Which means that I should be able to say you should theoretically. By the way, raining desert, appreciate the 10 gifted subs. No, the third bit is the most significant bit. Yes, it is. No, it's the third bit. One, two, third bit. The third bit is the most significant bit. This one right here. I even have it highlighted right here. No one does zero indexing, dog. That it doesn't make any sense to do zero indexing in this. Okay, you don't do you don't do that, right? because you'd want to go you'd be want to go when whenever you're doing shifting, you have to start at a one. If you don't start at one, you're just going to be confused, right? So, you do something like uh oops the other way around. Uh two to the power of the math, right? Which should be eight, right? So, that's the value we're looking for. Is that eight or am I wrong now? Oh, you're right. It is minus one. Okay. Yes, it's the third bit. It's the third bit. Okay, you're right. Hey. Hey, you're right. Okay, you're right. You're right. So, it would be uh Okay, I'm just gonna I'm gonna forgive I'm going to forgive myself because I love myself and I think I still think I'm a genius and you're an idiot. Wait, wait. Oh, that's cuz I double pounded it. I was like, wait, what? Uh, chat, you're still stupid, but I love you. All right, so yes, there we go. So four that would be the that's like the actual number because um here let's go like this. If I go uh two string two there we go and then go right here. If I do that you can see that right there. There we go. 001 most significant bit. Let's go. Feel sometimes wrong but but admits it a gen sometimes wrong. Hey I'm wrong. Still think you're an idiot though but I'm wrong. I'm wrong. Okay wrong. I got I can't do math. Um dude I cannot do math. Okay. So, this seems right. All right. So, now that we have that, that means I should be able to partition uh this table, right? Uh let's see. Partition R on N, right? And so what that's going to do is that's uh just just to make this easy, uh we're going to go like this. Uh R slice up to N and then from N to this, right? We we would effectively do that. So, I'd go uh uh const AB partition this one, right? That would be technically what I'd want to do, right? So now this gives me the A partition and this gives me the B partition. Correct? So now, how do I figure out where to go from there? That's what I don't understand is okay. So now I have the two partitions, right? So I should be able to go like this console.log A and B, right? There you go. You can see the two partitions, right? And it's true. V exists in here. U exists in here. So we did do this correct. We have partitioned the table accordingly to split these two away. So does that mean I got to go something like um what is uh console.log uh test a exit result test B exit result. I don't know what those are. One and nine. Okay. I'm getting further away. I'm getting further away. Shouldn't four be the upper bound? Yeah, I think I'm off by one. I think the partition is off slightly but it it's one based right because one is the lowest one so it's 0 1 2 3 4 5 6 7 8 right all right hold on okay how do I do this I I'm confused as to how do I do the final step of this problem all right what's the final step reducing the problem okay hold on hold on uh the set of all values where a uh is the i bit is one yes okay since u and be different position uh in position I we know that they have to be different in partitions correct. Next we can reduce another insight uh described earlier while we worked on integers uh one to n so far this is not required in fact the previous algorithm worked uh in any situation where there is one set of potential elements and two sets of element let's see and two a set of elements actually appearing this set may reduce or may only differ in one missing duplicate element. Okay, so how do we do this? Hold on. Let's just think about V again for a second. So if V equals 6, right? And what we have is we have the total which has 1 through N, right? Is which which has 1 through eight. And then we also have 5 through 8. Wait a second. So this would be partition B. Hold on. Does that mean A equals uh one through four? Right. Hold on. Look at that four go. Okay, four. That means we can take result xor a xor uv. Is that true? Because that would be uh that's 1 through 8, right? xord with 1 through 4 xord with u xord with v, right? which would reduce this down to 5 through 8. Xord with U, Xord with V. I still don't know how to get rid of this. I'm missing one step of how do you get rid of this because you don't get to I like I don't get to know V individually. I only get to know this as a combined value, right? I only I only get to know that as a combined value, right? Uh there's no I I I'm not I don't believe there is a uh SPF uh SPF 50 to get rid of UV. Oh, nice. I skipped a step. I know. I'm I'm Here's all the values I have. All right. I'm gonna call this one, by the way, let's just call this X, right? Which is going to be uh here. It's going to be uh V, X, or U. Okay, so that way we don't have to like resay these things. So, what is the thing I'm missing here? The goal is to find out U and V individually. These are the pieces of information we have. We know that we know that one of the one of the values of x either zero or one index into x appears in this one and the other one of x appears in this one. We just don't know which one. Oh yeah, just throw another letter in there. Well, we just know that part of x appears in one. We know part of x appears in the other one. I don't want to use you and v because it makes you think that you could just understand that v is in one of them. I don't understand that v is in the one of them, right? I feel like I'm learning something but I don't know what we're learning. Yeah, good rigor. Hey, we're trying here. We're trying to I I you know, this is why we do like this is why we read these articles cuz it actually is super awesome. Uh one partition key is missing. Uh exor uh all to the uh all to part Wait, hold on. We're learning to raid. Yeah, we're learning to raid here. This is literally what we're learning to do. I don't know how I've never raided before. I only know it. I only understand it in its very base case. The partition of a with the e bit is set has n numbers. The set of all values one to n with the e bit uh set has n plus one numbers. Wait, what the hell are you saying? Han, hold on, hold on, hold on. You filtered out, let's see, you filtered out values, not the partition, that uh have greater than four. Now go over all the values that have that are greater than four and exor them with five through eight. Find the single missing value. I don't dude, you're okay. So, I don't get it. This is like that draw the owl one. I don't understand what's happening here. Okay, so this is all. Yep. This is missing. Okay, good. We got this. I'm calling this X currently. Uh, which is three to six partition zero. Well, yeah, but I see I don't know how you're deriving this one. I don't know how you're deriving this one. I know, but see this. So, this is this is my problem. How are you deriving that one? Right. How how are you getting that? You're just like, dude, you just just have the set that has it. I was just like, "But Porqu and Maria." Oh, yes. I No, no, I get that. It's this. It's I'm not saying that filter. Look, I see that filter right here. It's this one right here. How did you derive that one, right? Maybe I Hey, I could be an an idiot. Find missing. Oh gosh, you had to do it in Rust, didn't you? You just couldn't help it. Way too horny. All right, set total. All right, there we go. All right, so that's a find double missing. Okay, set total. All right. A, X, or B? Find a missing. Okay, so this would Okay, so this is what I'm calling X. The least significant bit. Okay, so you're going to do the least significant bit. Okay, that's fine. Partition set of this one. Okay, so you're actually filtering based Okay. Okay, hold on. Hold on. Hold on. Hold on. Hold on. Hold on. Oh Oh, and All right. Okay. Okay. Okay. Okay. Okay. Okay. Okay. Okay. Okay. Okay. Okay. Okay. So, hold on, hold on, hold on, hold on, hold on, hold on. Uh, function uh we'll call this thing create. I'm not really sure what to call this thing other than create uh exor uh from mask, right? Right. And here's so here's n and the mask, right? So, this will be the because I assume we can go the other direction because you're doing it with zero. I assume you can also do it with uh one. So, what's happening here? Okay, so this right here would be the uh you're getting the least significant bit, which is kind of a funny way to do the least significant bit. Or that is the that No, wait, never mind. That's not the funny way. That is like literally the way to do it, right? I just show I just showed that one. Yeah. Or no, wait, hold on. This Let's see. This formula finds a Let's see. Later chap. This formula turns off. Oh, this turns off the right onemost bit. That's how you That's how you find the one rightmost bit. Okay. Yes. Yes, that makes sense. Okay. So, you're going to find the rightmost bit, the least significant bit. By getting the least significant bit, you then take the set of provided values and you get every provided value that does not have that bit. That means you know you're getting one of the two values out of here. Then you're going to go to the total set of numbers and get all the numbers that also does not have that bit. Which means that that Okay, so this Okay, see this is what I was missing. Oh, okay. That makes way more sense. This makes way more sense. Okay, so what's happening here? Okay, so I see this. So if you think about this, that means here, let's We have 0000 uh one. We have uh one zero. We have one one, right? We have one zero. Oh man, this is going to take a while to write here. I'm going to What am I doing? I'm going into Vim. I'm going into Vim. This is stupid. I have uh 00 uh one. Uh we have uh one. There we go. There we go. Awesome. All right. So that means uh u uh u v equals um what's it called? What what what value is that thing? The least the let's see and um minus u unv uh u uv equals that's going to equal one. Right? So it's literally the first bit that's the first bit that they have uncommon not common. So, if I go like this, if I go, we can ignore this first line, by the way. And if I go like this, if I do a one right here, and here, let's go like actually, let's go uh one with all these. Uh, and then give it a little uh There we go. Perfect. Uh, there we go. Okay. So, you can see this. So, these are all the values, right? Oh, I I only need to do it up to this, right? Well, I guess I because we're only doing zero to eight. All right. We're only doing these ones. All right. So, we get this one which equals one. That means in partition one, if we look for say things that don't have a one in that position, this makes so much sense. Okay, so this grabs the first the the least significant bit, we know for a fact that that least significant bit is going to uh if we grab all of them that have that least significant bit, then we've grabbed one side of our equation. So, we can just do the following. So we a we have the result which is going to be the exor of one uh one up to eight right I I'll represent that by this right so it's the xor of 1 through 8 this makes sense we have we have x which is just simply going to be u u v right and now we can create a partition zero oh my gosh we can call this one partition zero which is going to be the following which is going to be we're going to take this list I'll call this I I'll call this whatever this is right I don't know what to call this thing which is going to be 1 through eight and we're going to filter this by saying uh where x uh and uh and the lsb right equals we can do it as one or zero it doesn't really matter which side you do but by doing this what that will do here uh lsp uh stop right what this is going to do is this is going to split the table where there's just ones so I'm going to get every other one I'm going to get one three five and seven into one list. This has either U or V in that list and the other list has the other side. So now I know how to split them up in two separate lists that do exist one side or the other. Okay, so we can see that. Then we do the exact same thing, not just from the total list, but also from our missing list. Now remember our missing list, our missing list is going to look something like this, right? Our missing list is going to look something like uh this. There we go. So that means P. Uh so we're going to do this uh one to this one. And then I'll just call this one um whoopsies. I'll call this uh missing uh filter, right? I'll do the exact same thing. Let's go like that. And then I'll just call this one uh Oh, this makes so much more sense. Total, right? I'll just call it that. There we go. So, we have these two ones. So, we'll call this one uh PM01 or that would be pot and pal, right? So, that means pot literally equals uh it's going to be it's going to be 1 three uh 135 and 7, right? Uh pal is going to be it's going to equal 1 57. See what happened there? So, if you exor and pal, what do you get? So p 0t or uh let's see we'll call this we'll call this thing x0 right because it's just it's one of the two right so it's going to be uh pot uh pot xor palm right and there you go you now have discovered one of the two missing items which means I can then take my missing set right which I have my missing set right I can take my missing xor and then xor that with the total and this will equal X1. Oh, yeah. You could just do that. True. What am I saying? Yeah, I could just have XR1 equals X uh X1. Yeah, you're right. I'm such an idiot. It's obvious. Why did that make so much sense at the end when I was lost the whole time? It just does. This all makes this all Damn, that's cool. And now, how do you extend it to three numbers? Uh, that would be harder. My assumption is that you have to keep on you have to keep on part uh partitioning. I'm not really sure how you do how you would do it to three numbers, but that's crazy. Okay. Wow. Wow. There you go. The other missing number. Wow, that's cool. I I I don't think I understand how to do that. Oh, wow. That's cool. All right. Reaching the limit. One might try to take this further and aim to solve the problem for more than two missing values. I did not give this an abundance of thought but I think this is where we stop uh succeeding with exor. If more uh than two elements are missing or duplicated then an uh analyzing the individual bits uh fails because there are several combination uh possible for both ones and zeros. Yes, it'd be super hard to split them, right? You couldn't really split the table easily. The problem seems to require more complex solution which are not based on exor anymore. I assume this is just raid. This is a great article. Well, the great Yes, the greatness is I hope everybody really understands. Dude, if this is Rick rolling, dude. Okay, dude. I swear I was about to get Rick rolled. I swear I was about to get hit with like a strong Rick rolling. All right, anyways, this was awesome. Great article, people. Great freaking article. Loved every moment of it. Loved every moment of that article. The name is the primogen.