Closest Prime Numbers in Range - Leetcode 2523 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem closest prime numbers in range so I'm going to approach this problem kind of in two steps one is going to be like the math portion of this problem it's not necessarily something that you would easily be able to come up with but once I show it to you I think you'll understand most of it there's a couple optimizations in it that aren't like trivial I'll try to walk you through that it's going to have to do with prime numbers and then once you have that the second part of the problem is in my opinion aite code easy it's one of those things where like don't try to overthink it too much it's a pretty simple thing to do and I'm actually going to start with that because I want to show you that like you can take a problem like this one and kind of like split it up into two different things and even if you can't figure out one of the things you can still focus on the other thing so let's do that here what we're given is two numbers a left number and a right number and I think we can assume that the right number is going to be bigger than the left number and so in this example I think we have 10 and 19 what we want are two numbers in that range inclusive so for example like we could include the end points so somewhere in here we want two numbers that fall in here including this or this that are one prime and two the difference between those numbers is minimized so like the difference that's pretty much all that this is saying if there is not a solution we will return -11 if there is a solution we will return those two values that satisfy this criteria now there could be multiple answers and if that that's the case we will return the one that has the smallest like num one value and so by the way like the two numbers that we choose in there can't be the same number I think that's kind of stated like this by saying one of the numbers has to be bigger than the other number okay so now let's just think about this conceptually so we have 10 and 11 let's first just get all the prime numbers in that range like just kind of off the top of our head okay I think 11 is a prime number I don't think 12 is first of all what is a prime number let's kind of review that a prime number is a number such as seven which does not have any factors or I think the other word for it is divisor like a number that will divide seven there doesn't exist anything the only factors it has are technically 1 and seven and those don't count so the way uh people think of it is to say zero is not a prime number and one is not a prime number these are kind of like the base cases you could say that's debatable but I'm just kind of the messenger here these are not prime numbers and two is a prime number three is a prime number four is not a prime number because it does have a divisor to and we can kind of keep going I think five is a prime number six is not and then we just kind of keep going right so you you understand this hopefully knowing that we can continue with this so 12 is not a prime number I think 13 is I don't think 14 is I don't think 15 is I don't think 16 is I think 17 is though okay so now we have all the prime numbers that fall in this range now that I given you this you tell me how do we find the two numbers where the difference between those numbers is difference uh is minimized sorry so in this range how would I do that I mean okay you might think well the brute force is n s right you might think okay let me just put a pointer over here scan through everything thing let me put a pointer over here scan through everything etc etc not the end of the world if you're a beginner but I would say just take a second to think about that are you sure that that's the best way I mean think about this this assume it is sorted there's no duplicates so you tell me if I want to know what is the smallest like difference I could have with 10 I I don't need to go very far the number that's closest to it will be the pair that minim izes the difference so I'm just going to look at every adjacent pair I'm going to look at this okay the difference is one and by the way actually I I didn't talk about the fact that 10 is actually not prime 19 I believe is prime so we will uh keep that so yeah sorry about that but starting from here now we will look at every pair okay the difference between these two pairs is two okay fine so that's our result so far 11 and 13 okay look at the next pair difference is four that's bigger than the pre previous difference do not update the result okay next pair 17 and 19 the difference is two that's the same as this pair so based on the problem description you tell me which one of these would we return this one or this one if there's a tie we return the one that's the smallest AKA as we're going through this if we find that the difference is the same as a previous one that happened to be the result we will not update our result we will not say this is the result we'll keep this as the result 11 and 13 okay hopefully at the very least you understand that this portion of the solution is pretty efficient it's going to be linear time with respect to whatever the right number happens to be and more precisely however many prime numbers are in here now I haven't mentioned how I'm going to get those prime numbers but I think I'm going to quickly just code this part up for you and then we'll cover the prime number part because these are kind of very separate operations so I'm just going to assume we have a way a to get the primes that's what I'm going to call it and I'm going to call a function called get primes and I'm not going to implement this just quite yet let's just assume it gives me all Primes from left up until right including uh like these two so uh maybe a comma is better here so in this set it'll give me all the Primes from that now assuming I have that this is what I'm going to do I'm going to initialize my result to a -11 that's what we're going to end up returning and I'm going to have my diff which I'm going to initialize to Infinity cuz we're trying to minimize this difference so that's why I set it to a really big number I think if you don't want to set it to infinity or if you don't have that in your language I think right minus left probably also works let's just add a plus one to be safe but I don't think we actually need that plus one so um I mean maybe we do actually I think the plus one might be necessary but yeah I won't go super in depth into that but now I'm going to look at every adjacent pairs in the primes array so I'm going to have a right pointer or I could just call it the ey pointer it's going to start not at zero but at one because I'm going to do this and then it's going to go up until the end of the array and then I want to specifically do this primes at index I minus primes at index I minus one so the adjacent pair the current element and the previous element taking the difference now if this difference is less than the difference we've calculated up above if that's the case then I can do this this first I guess I can update the difference it doesn't really matter what order we do these but I can update the difference this minus uh this and then the result will be um updated to this primes at IUS one and primes at I I think we have to put the smaller number first that's why I'm doing it this way so this is pretty much the code that we need other than just getting the prime numbers and that is actually going to be a very standard algorithm this is what it's called sleeve of I'm honestly not even sure how to spell it and I'm even less sure how to pronounce it okay so this is it this is what I'm going to show you right now it's actually an easier algorithm than you might think let me show you why that is one way to get all the prime numbers from like one up until n or some kind of range one way to do that would be to iterate over every number so from one to two to three all the way up until n and then for one of these individual numbers I'm going to go through every possible number and check is that number a factor of this of course I'm going to skip one because one is a factor of everything but then I'm just going to check like let me take a more interesting example um seven I can check is two a factor of this does two divide 7 nope does 3 divide 7 nope does four does five nope none of these do once you reach the square root of a number you can can actually stop I'll cover that uh why that is in just a second but this is kind of like the most Brute Force way to do this I think the time complexity of that would be n Square t of n which isn't bad but they actually is a slightly better way and I don't know if it's slightly better it's actually probably dramatically more efficient but the time complexity of that approach is not going to be n log n it's actually going to be n log of log of N and the reason for that I think like I don't actually know off the top of my head I don't think you'd be expected to drive this in your interview but that is the algorithm that we are going to discuss right now Steve of uh this is what it is called so that's the one that is more efficient in terms of this so and if you're wondering like how does this compare to like just n log in which we are more familiar with this is actually more efficient when you take the log of a number you're making it smaller generally speaking I mean when you take the square root of a number you're also making it smaller but when you have two logs stacked on top of each other that's going to be more efficient than just a single log and in case you're curious about the math like how does the square root compare to something like log base 2 of n so square root of n versus that well think about this for a second if I take a number 2 to the power of 64 for example and I square root that well I'm going to get 2 to the^ of 8 because 2 power of 8times or actually I no I forgot how my math Works sorry I'm going to get 2 the Power of 32 because if I take 2 the^ of 32 and I multiply it by 2 ^ of 32 then I'm going to get 2 the Power of 64 you could also think of it as like raising this to a fraction that is 1 12 this will multiply that it'll be 2 ^ of 32 so you see that right you see that this will be 2 to 32 Well Log is going to do something crazy log by definition means that like this is equal to X and that means that 2 to some power x is equal to n and if I take the log base 2 of both sides I basically cancel this out and I get X is equal to log base 2 of n okay maybe I just confused even more here but long story short if I took log base 2 of n where n is 2 ^ of 64 2^ of 64 what is this going to equal again log by definition says 2 to what power is going to be equal to n well we literally see that over here 2 to ^ 64 is going to be equal to 2 to^ of 64 so this will turn into 64 now you tell me which one of these is smaller this one so this grows much more slowly than the square root of n so the whole reason that I went through this was to show you that the algorithm I'm showing you is dramatic Al more efficient n * log of log of n is going to be much smaller than nunk of n it's not even close okay with all that said what is the basis of the algorithm well it's actually kind of simple with our previous thing as we were kind of going through these numbers for each one of them we were trying to determine is a number prime or not like that's Prime this is not well the seeve algorithm it kind of inverts that thinking so it does the opposite instead of determining which numbers are prime it will determine which numbers are not Prime in a given set in a predefined set of numbers it'll determine which ones are not prime this is how it's going to do it so remember how we were given our left and right boundary so in this case we had 10 and 19 so I want to get all the prime numbers up until 19 that's just how like the seeve algorithm works it just takes an upper bound so you can think of it like this we have an array and we pre-allocate it it's actually going to be a Boolean array and initially everything in here so for each index everything is going to be true and that just means that we're first saying okay assume every number here is a prime number and then uh we're going to say okay well at the very least I know that zero and one are not prime so let me just change those to false this is false and that's false and then what I'm going to do is something very clever I'm going to say okay starting at two which I do know it's a prime number and like I said assume everything in here is true initially I'm going to take two and now I'm going to do something like this I'm going to take every multiple of two and say well I know every multiple of two is not a prime number because they have two as a factor so it's very simple in terms of the intuition so this is what I'm going to do I'm going to say okay well 2 and four and six it's going to get kind of repetitive here so I won't just talk through all of it but all of those are not going to be Prime and then I'm going to do the same thing a starting at three I'm going to get every multiple of three and say that these are not prime so I'm going to go to Six I'm going to go to nine you see that we did see that number multiple times that's fine so we go to 9 now we go to 12 then we go to 15 then we go to 18 and then we would stop once we go out of bounds I'm just going to do the exact same thing here starting from four and this is where you'll see some repeated work um starting at four we could do the same thing so I could do four and then to eight and then uh to 12 and then to 16 and then to 20 and then we're out of bounds I could do that but do you see something here this time when we started at four every single number that we saw was already marked with false you can tell because it had a blue on every single one and why was that because this is very interesting this is a slight optimization and this is probably the hardest part because hopefully intuitively you understand why this works but the optimizations are kind of the hard part of this algorithm notice how four the number that we started at it was already marked false why was it already marked false three was not three was not already marked false because three is a prime number four is not a prime number and we actually already determine that and we determined that because two is a factor of four two is a divisor of four and so we already did two we already did all the Hops for two so we don't need to do four because every single multiple of four of 4 8 12 16 every multiple is going to be a multiple of two right it's it's basic math it seems kind of complicated at first but think about this if I have like seven for example I'm starting with a unusual number and I just get every multiple of seven and I go to 14 I go to 21 and then I go to 28 then I go to 35 and I just keep going well now if I start with a multiple of seven let's say it's 14 then I'm going to go to 28 then I'm going to go to 42 etc etc well 7 already covers everything so I don't don't need to do that so that's the idea that's one of the optimizations that's like one of the small optimizations here and so that will allow us to not do like too much repeated work and so just continuing now with this algorithm we skip four we uh get to five now and we'll do the same thing okay five to 10 to 15 and even though like all of these were already marked as false that's not guaranteed to be the case because now we could have gone I think eventually to something like a 25 which would not have been marked based on like the previous numbers so yeah just keep that in mind as well and now we could technically keep going we could iterate over the entire thing and for each of these numbers end up doing that but based on our upper bound we actually one thing you might think is we only need to go halfway because then from 10 and then we would get to 20 and then all of these if you double any of these they would end up going out of bounds so you might say okay well just stop at the halfway point and that's reasonable stop at n / 2 but I'm actually going to tell you that there's actually a better early stop and that stop is actually at the square root of n the reason is again just some Factor math some divisor math let me just kind of briefly explain it let's just take a even kind of number for this example let's say I had the number 100 for a second I'm saying I only need to to do this kind of like the multiples I only need to do that from 1 to two and all the way up until 10 because 10 is the square root of 100 why do I not need to do that for 11 and beyond that well it's very uh very subtle and so I I think I might need a little more space to explain this so let me make space really quickly sorry and by the way if you don't understand like these minor kind of math optimizations I'm making it's not the end of the world just try to kind of understand like the core algorithm which I'll finish up in just a second but think about this for a second if I take one and or well we usually skip one we start at two and then we take every multiple of two right 2 4 6 8 we do that with every number why do we stop at 10 why don't I continue with any number beyond that so in this example if I have 100 why will I stop at the square root why won't I do that for 11 it's very subtle but let me show it to you if I had 11 well let me just get all multip of 11 so I'm going to double 11 I got 22 I'm going to Triple 11 I got 33 I'm going to quadruple so I'm just going to kind of keep going and pay attention to the words I just said so I wish I didn't have to write all these out but I will just to really drive the point and so now I'm going to stop because now if I take one more multiple of 11 I'm going to get 111 and so that's obviously out of bounds so I stop do you notice anything about these numbers well 11 I mean we don't really Mark the number itself as false so uh Let's ignore this one but when we take every multiple of 11 like these are the multiples that we are going to Mark false well I just doubled 11 so 22 doesn't 22 have a factor of two didn't we already do that when we took all multiples of two well I think we did and what about 33 isn't that just triple 11 thus it has a factor of three thus we already did it when we stopped at 10 same thing here 4 5 6 7 8 n and we never go beyond that that's why we can stop at the square root of the number because every other number will have already covered all the numbers before that will have already covered all the multiples we're looking for for every number beyond that anyway so again this is just math this is one of those things that some people like some people don't if you don't like it it's going to probably be hard to understand this I don't blame you if you don't but I just wanted to mention that for the people who are interested in kind of having a deeper understanding of why these things sort of work because it's not magic it's just math so uh anyways let's uh finally wrap this up now so assuming uh we did that we had kind of a true true or false we would have a false for every number that's not prime so then we'd be left over with the numbers that are prime let me just kind of circle those uh in purple so we got this Prime this Prime this Prime three is prime five is Prime Seven is prime I don't think any of these are prime but 11 is prime 13 is prime 17 is Prime and 19 is prime so now we could collect all of these purple values into an array but remember that our boundaries are 10 and 19 so we only need the values that are like Prime within this range so we can kind of just cut everything off over here and just get 11 13 17 and 19 and then once you have this it's as simple as what I showed you earlier the pair wise difference so this and this and this so now let me show you how to code this up okay so almost done here now we just have to implement that get primes function I'm going to try to make a little bit of space so this is what I'm going to do let's just call it get primes I'm not going to pass in any parameters into it we are going to be using the left and right parameters they will be accessible in the function so I'm going to have my is prime array and I'm initially going to set it to true for everything and I'm going to set the length of this not to be right but right + one because we do want to include that right index and we know this starts at zero so that's why we will initialize is Prime at zero well I don't need the S and is Prime at one and set these to false now is that Prime part that I was talking about remember we're going to start at two so n in range from two you could go up until the limit so for python uh we would do WR + one because this is a non-inclusive but remember I said that we actually only need to go up until the square root of this number so that's what I'm going to do I'm going to calculate the square root python makes it pretty easy there's a function called square root and this might be a decimal so we want it to be an integer and I think this will round down which is fine and again this will not be inclusive in Python the way the range function works so we will have that plus one here so with all that now what we would do is now get all multiples of n starting at n + n so for let's say m in range starting at n + n we have no idea if M itself is not a prime number we're just taking this number and getting every multiple of it because we know that that multiple is definitely not prime so then we'll do this and we'll keep going up until the end which is right and I'll do the plus one that's how python works and this time like we don't want to increment M by one every time that's what this range function does by default so by passing a third parameter into this with python this will be the increment and we will increment not by one but we will increment by n so that's what I'm going to put here and then I'm done and then I can just mark this number M as a false so the other optimization remember was if we have a number like the starting point here if n has like all of them started as true but if this number itself is not prime so not is prime n if that's the case we don't actually need to execute this part because we know that there was a factor of n that already marked this guy as false and thus it already marked every multiple of n as false anyway so we can skip this is another one of those minor optimizations that is kind of hard to reason about if you don't like math and that's that's really the hard part of like this aive algorithm the core idea is pretty simple but like this optimization and this optimization are not simple to reason about if you want to just memorize them I think that's fine um but anyways so so once we have that then we just want to collect the values in this array that are prime still so let me have my array called primes this is what we're going to return out of this function and then I'll say for I in range length of is Prime and then I'll say if uh this number is prime well then we want to add it to the primes array but let me also just confirm that I'm taking that number I and adding it to the primes right and let me confirm that that I is at least greater than or equal to left because we know that everything is going to be less than or equal to right but now is when we finally check that these numbers are greater than or equal to the left so then when we actually call this function down here we can ensure that those numbers are prime and they are in that range and then the rest of this code should work so let's give this a run and you can see here it works it's pretty efficient I think there is like another solution or maybe this person is using like some like bit manipulation things but but anyways I think this solution I talked about is definitely satisfactory for a medium problem it's pretty efficient if you found this helpful definitely check out n code iio thanks for watching and I'll see you soon