Prime Subtraction Operation - Leetcode 2601 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem Prime subtraction operation this is an interesting problem a decent amount of math but also some conceptual challenges with this problem I'll be showing two solutions one is more of a Brute Force solution but it actually does pass on elak code and I would say that honestly a Brute Force solution given that this is a medium problem isn't the worst thing it very well may pass you in the interview I will also show you a second more optimized solution which maybe for a medium problem you might need a hint to uh come up with the solution so we're given an input array all of the integers are going to be positive that's guaranteed we want to transform this array well we don't actually want to transform it but we want to know if we can transform it such that it will be sorted in strictly increasing order not non-decreasing order where like adjacent elements could possibly be equal that's not allowed they have to be in increasing order so is it possible to do that well the rules of the game are this we can pick any element and we are allowed only to subtract from that element and we're only allowed to subtract prime numbers so knowing that how can we solve this problem I'll kind of walk you through my line of thinking it was this if we pick an element first of all we can pick in any order that we want but it probably makes sense to go left to right so that way we can kind of validate okay this portion was sorted this portion is sorted now this portion is sorted etc etc so we could start from the beginning of the array trying like a root Force approach we look at four it's already sorted right like the next element is greater than four the previous element doesn't exist so we're good so okay move to the next position nine it's greater than four but it's not less than six so we should subtract from here uh there's a prime number I'll just randomly pick one seven we could subtract seven from nine then it would become two okay that's technically less than this but it's not less than the previous or it's not greater than the previous value so now you might think okay this seems like a backtracking problem right so I have to Brute Force this I have to make a decision tree I might have to go back but no that's actually not the case we can instead of going back to two and seeing okay well is there a prime number I can subtract from four yes there is we can subtract three from four and then it'll be one and then this portion of the array is sorted instead of having to backtrack and do that why don't we just be greedy we just want the array to be sorted we don't necessarily know what's coming up ahead we really don't I mean there could be some really small values here for example like this could have been a three so what kind of greedy approach should we take knowing that we can't predict the future we should try to every time we look at an element not only should we try to make it such that it's sorted like it's less than the next element and greater than the previous but we should also try to minimize each element how are we going to minimize each element well we can only subtract prime numbers so thus we will choose the largest prime that we can subtract from each element as we go this way we don't need to do any backtracking or anything like that by the way one thing I didn't mention earlier is that yes we're allowed to subtract Primes from any of these given numbers but we also want every value to remain positive so we can subtract like the largest possible Prime but if a number itself is prime like for example if we had seven we are not allowed to subtract seven the largest prime we would be able to subtract is 7 minus one which is not a prime number just keep that in mind so knowing all that this is how we can solve the problem okay for the first number four what's the largest prime we could subtract from four well we can Brute Force just getting every number that's less than four so 1 2 3 these are all the numbers less than four in other words this is the upper bound of all the numbers less than four and so among all of these we want to figure out which one of them is the largest prime so we can kind of go through these in reverse order check is this a prime if it is then we can stop we found the largest prime if it's not the largest prime we will go left and try to see if there are any primes here here now in this case three does happen to be prime so three is the number that we would subtract from four now how would you determine that a number is prime well the root Force way to do it would be like this a number n is considered Prime as long as there doesn't exist a factor or denominator that can divide it such that like the remainder will be zero so does there exist an F if it does then this is not Prime and if there does not exist an F then this guy is prime how do we check that like this just get every factor from two all the way up until uh this number but actually if you want you can stop early going all the way up until the square root of that number cuz we don't need to check any factors beyond the square root and if you want the intuition of why that is consider something like 49 where the square root of it is 7 so we would only need to check up until s because anything else like for example even if there was a factor over here it must be multiplied by a number that's less than the square root and if you know this is a factor then we would have already found the factor here and that's why we can stop at seven so knowing all that now we can solve the problem assuming we have a way to find the largest prime we can do this take three now subtract it from four uh we're good we'll have one here and now we'll move to the next position we want to know what the previous element was because we do want to make sure that this is greater than the previous element so now from here we want to do the same thing just remove the largest possible Prime and in this case that happens to be seven so if we subtract seven from nine we will get two and that is greater than the previous element but it could have been possible that maybe we got a number that was less than the previous element an easy way to avoid that is rather than checking all prime numbers from like 1 through 8 remember we skipped the nine because we don't want to set this to zero rather than checking if these are prime numbers we know that if eight happened to be a prime number we would not want to subtract it from nine because if we did we would end up with one here we want the array to be in increasing order this is not the case so what we actually do is we take the current element nine subtract it from the previous element 9 - 1 that gives us 8 so now I'm going to check all numbers less than 8 so 1 through 7 and check if any of those are prime so you can kind of think of it as like this being the upper bound of numbers that we need to check and the upper bound is not inclusive so basically we check everything less than that and I know I said 1 through 7 but I actually meant 2 through 7 cuz we already know that one by definition is not a prime number anyways now let's code it up I'll just leave these comments in case they're helpful but we can get started now I'm going to define a helper function is prime so that we can determine if a given number is prime because remember we are going to kind of Brute Force this so given n is it Prime for now I'm just going to assume that it works and we're going to use it to solve the rest of the problem and then we'll come back and fill it in I want to go for n in nums every number I want to calculate that upper bound I was talking about so I want to take n and subtract from it the previous numbers so I'm just going to have a variable for the previous number initially we can just set it to a neutral value like zero we already know that zero is less than every number in the input because every number is going to be positive and we also know that since it's a neutral value like zero it's not actually going to change the value n and this is the upper bound but remember the upper bound is not inclusive so this is technically not the largest number that we could subtract from n this is non-inclusive I'll just make a comment for that non-inclusive the largest prime we could subtract is technically this minus one so keep that in mind but when it comes to python it won't be a problem you'll see why so I want to figure out what is the largest prime again I'm just going to initialize it to a neutral value like zero basically saying we have not found a prime number yet so now I'm going to check every number for I is I a prime number I'm going to go from two up until the upper Bound in Python this second parameter is not inclusive so so this Loop is going to check everything from two up until upper bound minus one we skip one because one is not Prime and also for this we could go from left to right but it would probably be better to go from right to left because we're just trying to find the largest one if we find one we can just break out of this Loop so I'm actually going to take this and reverse it and then in here I'm going to call is Prime on I if it is prime I'm going to set largest prime equal to that number and then I'm going to immediately break out of it as soon as we find a single prime number we break because we're checking from largest to smallest now after that is said and done this is the largest prime we were able to make we should check that n minus the largest prime because remember that's the whole point of finding the largest prime to subtract it from n if this is greater than the previous number well if it's greater that's good but if it's not greater if it's less than it or equal to the previous number that's bad we return false because that means it's impossible to make the array in ascending order and so then down here if we didn't execute this return statement we can then actually update uh the previous number set it to be n minus the largest P so that it can be updated for the next iteration and this is pretty much it if we never return false here then we will assume that we did indeed put it into sorted ascending order and the only thing left for us to do is to fill in this little helper normally with an is prime function you'd want to add like an if statement to check if the number is less than two or even if it's negative then you would want to return false we say that that would not be a prime number but the reason we actually don't need to add this this time is cu we already start at two anyway we'll never go below two when we pass like I in as a parameter so we don't need to do that so I'll just not put it there then we want to check every Factor of n from two up until the square root of it so for f in range from two up until the square root of n which could be a decimal so we want to round it and this will round it down converting it into an integer will round it down if it's a decimal and since this is non-inclusive in Python we will just add like a plus one here because we do want to try the square root we know that that's a factor of N and we want to determine if that's a prime number so we can determine if n is a prime number if it can be modded by the factor that we are choosing and if that remainder equals zero then n has a factor of f so it's not a prime number we return false otherwise if we never find a factor we can return true that means it is a prime number so this is the entire code let's give it a run and as you can see it works and it's actually relatively efficient if we analyze the time complexity we can clearly see this Loop is going to iterate n times so big O of N and the inner loop here is going to iterate this many times the upper Bound in the worst case what could the upper bound be well proportional to n an element inside of the array so what's the max number inside of that array that's kind of what this is proportional to so we'll call that M so n * m now inside of this loop as well we have a function call and unfortunately that function call actually has a loop inside of it as well but this one isn't so bad what we're passing into it is a number in the worst case again it could be the maximum number but when we iterate we're not iterating M times we're iterating the square root of that number so here we'll do uh times square root of M so this is the overall time complexity so it depends a lot on the max number square root usually isn't uh super inefficient this might be inefficient though so in terms of optimizing this solution I'm actually going to show it to you just in this code because I honestly think it's easier to explain in terms of code most of this code is pretty straightforward I think one of the big bottlenecks we can see here is we're calling is Prime on a bunch of numbers for example this sequence from two up until upper bound maybe one of the times we do that it'll be something like this from two all the way to seven and maybe the next time we do it it'll be two all the way to four and maybe the next time a two all the way to 9 for each number in this range we're going to determine if it's Prime we're going to ask is two a prime number is three a prime number is for a prime number and clearly it's repeated work we're doing it multiple times so why don't we just precompute those prime numbers and then we won't have to make this function call well how do you precompute it how do you know how many numbers to pre-compute in the first place well without using like the constraints of this problem which is kind of a shortcut we can clearly see that whichever like end value among all of these is going to be maximal is the one that we would choose this is like the upper bound and what could it possibly be as the max value well N is a number in the nums array so the max value in the nums array minus zero because that's like the smallest that this could be so we only need to compute prime numbers up until then up until the upper bound and really we could probably do upper bound minus one so that's exactly what I'm going to do I'm going to do some pre-work up above here rather than calling this uh here I'm going to create an array which I'm going to call primes we already know that zero and one are not prime so I'm going to have an array and fill the first two values with false what this array represents primes of I is going to be true if I is equal to a prime number so we're going to go through every number for I in range 2 up until the max in the nums array this is technically not going to include the max number number because we know that in reality the upper bound is going to be the max number minus one like that's the highest it could actually be so that's why it's done this way you could do a plus one here it's not going to hurt but anyways we want to know is this number Prime let's do the function call let's check if is prime I and if it is let's set primes of I uh to be true and we actually have to append in this case so I will do that append this to True otherwise append it to false and this works we did the precomputation so now we're going to make an intelligent decision down here instead of making a function call which we know is square root of n we're going to do a array lookup which is constant time so rather than is this Prime let's use the array primes at index I and then the rest of the code stays the exact same so I'll just quickly run this to you to prove that it works and you can see that it does I believe the runtime actually might be less than the other one but anyways and in terms of Big O runtime this is more efficient I'll quickly analyze it analyzing this part here we can see we're still uh looping n times in the outer loop so we're going to get n and the inner loop we still have that inner loop which is going to iterate M times so n * m and plus uh for the work that we did up above here we're iterating M * the max number and then inside of there we're calling is prime we know that's square root of M so this part is m Time Square < TK of M so it is an improvement you can see that the largest term up above is going to be larger than either of the terms down here given the fact that like all of these are going to be integers and not like decimals that are less than one now you might think you're done but actually there is a way to do it even better we can get rid of this Loop in here as well and that's actually going to require being a tiny bit clever we can actually make this array a little bit better because what we really want to know is with this upper bound what is the largest possible Prime well in reality we're doing upper bound minus one because we know in Python these Loops this is not inclusive uh but anyways what I'm trying to say is I want to change the definition of this array up above I want primes of I to be equal to the largest prime that is less than or equal to I this represents the largest prime less than or equal to I cuz if I had an array like this if I had one this is what I could do I could just say down here don't give me a loop I don't want that largest P I already know what that is I pre-computed it for this particular upper bound it'll be this uh upper bound minus one because again that upper bound was non-inclusive that's how we defined it originally so now the only thing is how do we build an array that satisfies this definition well let's say I was trying to determine is a seven Prime like I is equal to 7 so let's just do that I equal 7 is 7 Prime because if seven is prime then obviously that's the largest prime that's less than or equal to I like that's the largest it could possibly be so that's what we should check first and if it's not well then the largest prime less than or equal to 7 is going to be the same as the largest prime less than or equal to six because remember this isn't prime factorization we're not checking if that prime number is a factor of this we're just checking what's the largest prime number that is less than or equal to this and if seven is not prime then get the largest prime less than or equal to six so this is how we would compute it for the first two positions I'm going to put 0 and zero because we know that 0 and one technically don't have like prime numbers that are less than them but then we will Loop similar to how I've done it below actually from two up until the max number and we check if that number is prime then append to this array the number itself it's the largest number that's Prime less than or equal to that otherwise we will append to it the previous Prime at ius1 now the base case is really two because two is a prime number so we're going to have two appended here and then we'll just kind of keep going we'll say okay now give me three okay now is four a prime number nope so the largest number that's less than or equal to to four that's Prime is actually the previous number three then we'll check is five a prime number yes it is five is a prime number six is not so we give it a five is seven a prime number yep so that's just kind of the dry run but this is pretty much it that's the whole code and this further time complexity you can see that the pre-work we're doing up above is still technically M * the < TK of M but the loop down here is just n so for the new time complexity we have is this getting rid of that and and this this is the final time complexity of the solution I'm showing you right now and it's definitely an improvement over the previous like first one that we had let's give this a run you can see that it works I guess the run time on leak code was worse than the others but I can confidently say that at least Big O run time this is more efficient if you found this video helpful definitely consider checking out n code. it's got some really incredible free resources you can see that it definitely took a lot of time to like create this stuff and I honestly think it'll be valuable for you if you haven't heard of it I know most people have already heard of it uh but still worth mentioning thanks for watching and I'll see you soon