Insert Greatest Common Divisors in Linked List - Leetcode 2807 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today and you better not skip this video because we are finally going to be doing my favorite subject some math let's get into it insert greatest common divisors into linked list very very straightforward problem conceptually but the math I'm going to show you probably isn't easy but I think you'll understand it by the end of this video and who knows it might blow your mind take a look at this link list all we want to do is modify it all we want to do is insert a node here here and here between two adjacent nodes and we want to give it a particular value which is the greatest common diviser and we'll talk about that a bit more in depth but just to kind of go over the basic part imagine we have a pointer we're maintaining a pointer we're here this is our current pointer we're going to insert a node here only if there exists a next node if the next node is non null okay then what do we do well we take the next pointer here and set it to the new node that we're creating and we set the next pointer of that new node to the next node of this node so that's going to require a bit of pointer manipulation but nothing crazy the code will be pretty straightforward and then when we update our current pointer remember now that we have this node extra we can't just shift by one we have to shift by two so that we get to this node then we can insert a new node in between there and then after we do that it's going to look something like this the blue nodes are the new ones the values matter though the value has to be the greatest common divisor between these two so a number that divides this and divides this without a remainder that happens to be six because think about this for a second the greatest common divisor between these two can't possibly be greater than the minimum of them right like this could be the largest possible value that we have okay and then you know a brute force would be just counting down from here try six try five try four try three etc etc that would be Big O of n where n is not the size of the list but let's say n is the value of this I guess I'll call that M obviously in that case the time complexity is going to be n * m because we're going to insert roughly the same number of nodes that we have in terms of like the size of the list and if each node takes this much to compute like the value of that node that's going to be the time complexity but there's a algorithm a math algorithm called the greatest common divisor algorithm it's ukids algorithm for doing that a very famous mathematician and that algorithm actually runs in log M time where m is the minimum value between those two that's actually a built-in function if you just want to call the built-in function that's perfectly fine but I want to show you how to you know implement this algorithm from scratch it's not that long it's like literally three or four lines of code most people can probably write it out and if they can't they can look it up and then memorize it or whatever but I want to explain to you why it works I want to clear every doubt in your mind and don't you dare skip over this part suppose we have two numbers 48 and 18 their greatest common divisor I'll just just tell you is six but how do you compute it and how do you do it efficiently well let me I'll call this a and I'll call this B but this is the bigger number and this is the smaller number but ultimately this is what we're trying to do the first thing that we could try is just check if this number divides that then we're done right because this is the largest possible Factor we could have so if this divides that then we're good right now it doesn't right if it doesn't do that we care about what the remainder is the remainder is the key so I'm going to write out a formula there is some value it could be one the greatest common divisor between these two numbers could be one like for example with three and seven the greatest common divisor is one it could be one or it could be something else but whatever it is we call it g the greatest common divisor if B does not divide a then we can't just write a very simple formula like a / B is equal to X where would be the greatest common divisor we will have a remainder and that remainder can be kind of summarized with this equation like in this concrete example 48 / 18 well I think that's going to be two with a remainder of 12 the reason being 18 goes into 48 two times and it becomes 36 but if we add another 18 then it's going to go over 48 so the difference the remainder between these two is of course 12 that much makes sense sense so if we take the bigger number and mod it by the smaller number we will get the remainder of course in this case that's going to be 12 now I'm going to tell you why the algorithm works and then I'm going to prove it we started with these two values we're trying to find the gcd of these two the next step is going to be for us to take these two values and find the gcd of them until we get to a point where we can do this operation and get zero cuz if the remainder is then zero then we know that the smaller number divides both of them and then that number will be the result and you can kind of tell that this is going to be efficient it can't possibly be more than log n cuz we're taking a number and dividing it how many times can you take a number and divide it until it reaches one or zero well that's like by definition of log n and the base in this case actually is going to be bigger than two on average but anyways now let me prove to you why it'll work I'll just kind of simulate the rest of it so now we have 18 and 12 so now I'm going to take 18 and then mod it by 12 I get a remainder of six okay now I take these two numbers do the same thing I get 12 mod it by six now I have zero okay this is the magic number we got six this is our result but why does it work well it kind of goes back to this formula and a couple key points the first point is that any number that is a divisor of A and B is also going to be a divisor of B and R let's think about the extreme case where B is the divisor B is the divisor of a well in that case r would be zero and technically any number is a divisor of zero and point two is kind of the opposite of this any number that's a divisor of BR like a common divisor is also going to be a divisor of ab now if these two things are true the reason this is important is because if these two things are true then that means that the greatest common diviser of A and B is going to be the same as the greatest common divisor of B and R so essentially we're taking a big problem and turning it into a sub problem and we're doing that repetitively until we get to a smaller problem that we can actually solve and understand so now let me quickly demonstrate to you why these two points are true take a look at what we're doing over here when we have 48 and we're modding it by 18 we're doing this we're saying okay minus 18 1 okay it's it's uh 30 it's still greater than 18 okay minus 18 again okay now it's 12 okay now it's not greater than 18 so now we're good isn't it true that if there's a value I'll call it g or F like a divisor or a factor if it's a factor of 18 that just means that we can take that number multiply it by something and then get 18 in other words like if we sum this up a few times I don't know how many times but then we can get to 18 for example 6 is a factor of 18 you add six three times and you'll get 18 and suppose that that factor is common to this one as well so now I'm going to use the names for these this is a this is B so basically some value G exists which multiplied by let's call it X1 will equal a like that's the definition of a factor and let's say this is the greatest common factor and it's also a factor of B so b equal to G times let's call it X2 some number is going to equal B I'm starting to run out of space so I'm just going to use this like white line as a boundary so now I'm going to do a minus B and that's going to be this minus this but I'm going to factor out the G I'm going to say G is this X1 - X2 so what this proves here is that any difference between two numbers Like A and B if we take the difference between these that difference is going to have G as a factor right and so when we are doing the mod operation down here that's essentially what we're doing we're taking the smaller number and subtracting it from the bigger one so of course we expect these to have the greatest common divisor and then we do that operation multiple times and of course that should also have the greatest common divisor so I just proved to you 0.1 anything that divides A and B is also going to divide B and r i mean the fact that it'll divide B is Tri trivial but I just prove to you that it's also going to divide the remainder now I'm going to prove to you the second Point down here and this I'll do quickly suppose there's a number that divides R and I'll say R is equal to G * X1 actually I'm going to do X2 just because we know R is the smaller number in this case and I'll do the same thing over here B is equal to G * X1 now if you were to take these two um formulas substitute it in this you'll get something like this a is equal to this * Q I'm going to factor out the G I'm going to put G out there and then on the inside I'm going to have X1 * q and I'm going to put this replace it with r and I'm going to factor out the G so this is that so G the greatest common factor of B and R is obviously a factor of a I mean this formula kind of proves it you can divide both of these by G this formula proves it g * some number this formula is going to be some number is going to equal a so I just proved both of these to you I just proved that this algorithm works and I'm going to codee it up for you now and you're going to realize how trivial it is so let's code this up first things first let's just do the gcd part because that's going to be harder than the rest so I'm going to start with that while it's still fresh in our mind okay we have these two numbers let's assume that a is bigger than b and I'm going to do this while B is greater than zero eventually it'll reach zero we're going to do this we're going to replace a with B we're going to replace B with a a modded by B by doing it this way we preserve the fact that this is always going to be greater than or equal to this one and we're doing it iteratively because we don't want to do it recursively and lose U memory though it's possible to do this recursively and that's literally it so now you tell me what's the return value going to be are we returning a or b well B is eventually going to reach zero when it does a is going to be the greatest common divisor between them and we know it's the greatest common divisor between them because of the sub problem when we start with A and B and we replace them with b and the remainder those two numbers are guaranteed to have the same common divisor and so we keep doing this we keep solving the sub problem until we reach the base case when one of them is zero then the greatest common divisor between them is going to be the one that's nonzero so that's why it works and down here is going to be the easy part the link list part so current is going to be at the beginning of the link list while current. next is nonnull the reason why we don't just do while occur is because we want to insert nodes between two nodes so there must be a next node for us to insert the node into so I'm just going to get the two values between the nodes current and the current.next value and then I'm going to create a list node I'm going to give it a value of gcd of the these two so I'm going to copy that do gcd of these two and then I'm going to pass in for the next pointer of this new list node that we're creating I'm going to pass in the current uh next node so that it can be connected with it and then this I'm actually going to assign to current. next and then after that's done I'm going to shift current by two I'm going to set it to do next. next and at the end we want to return the head of the length list the head is not going to change because we're only inserting nodes between two adjacent noes we don't need a dummy node in this problem just return the original head now one question you might have if you're clever is how do you know I put the max here and I put the Min here what if I put the smaller one what if I put 18 for a and I put 48 for B what's going to happen let's look at it well a is going to be assigned to B A is going to end up being 48 and B is going to be assigned to 18 moded by 48 now you tell me what's the result of this mod it's just going to be 18 if you take a smaller number and mod it by a bigger one it's just going to be the smaller number so the Beautiful the elegant thing about this algorithm is it'll actually fix itself if you pass it in in the wrong order it'll still work I mean isn't that so beautiful I would even say it's better than sex not that I would know of course anyways let's finally run this and you can see it works and I promise you it's pretty efficient I think I probably had too much fun making this video anyways have a good day I'm going to go back to working on my system design newsletter