Power of Two - Leetcode 231 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem power of two we're given an integer n we want to return true if it's a power of two otherwise we want to return false and a power of two is just basically two raised to any power and so two to the power of zero by the way is one that does technically count as a power of two 2 to 1 is two then it'll be four then it'll be 8 etc etc so if you're familiar with how binary numbers work two is very related to this and you might want to consider like negative exponents what about 2 the Nega 1 well that's technically 1/2 but we are told that we're given integers only so we don't worry about negative exponents now the most straightforward solution to this problem is to do some kind of loop just like I showed a second ago we can try every possibility 1 2 4 8 and then go through all of the possibilities until we get to 2 to ^ of 32 and the reason for that is that n is not going to be any bigger than this and it's not going to be any smaller than -2 ^ of 32 where this is the number and then the negative applies to that we already know we don't need to consider negative numbers so the first thing we can probably check is is the input at least greater than zero it has to be that for it to be a power of two and then we basically consider all of these now how many times are we going to have to loop it's kind of obvious if you know your math probably 32 times so it's not a Force solution at all and that's because exponents grow very quickly so this is the easiest way to solve the problem in my opinion we can also check that n the current or whatever current value let's call it X or whatever once it becomes greater than n we can probably stop searching if it becomes equal to n we can also stop searching but while our current number is less than n we're going to continue to multiply it by two to get all the possibilities so this is technically a constant time and space solution so let's code it up so like I said the first thing I'm going to check is n greater than 0 well if it's less than or equal to Z then we can return false immediately otherwise I'm going to declare a number I'm going to call it X you can call it whatever you want and while X is less than or equal to n we are going to multiply it by two so X multiplied by two now in here we could check if x is equal to n Go ahead and return true stop it immediately but out here it could be Poss that at some point x becomes greater than N Out Here we might want to return false now the easier way to condense this code and I guess it's not easy it's just a way to condense the code is to get rid of this and take this part cut it then get rid of this line replace this with this this way the loop will terminate if x becomes greater than n or it becomes equal to n we don't know exactly which one of those happened which is why we're going to return this this comparison is it equal to n or maybe it's not ALS also you realize that we don't really need this either because if n is truly a negative number this Loop will never even execute X is one it'll never be less than or equal to a negative number or equal to zero and so this will return and it'll return false so we can actually get rid of this too so this is the entire code not a lot of it let's run it and it unfortunately looks like I missed one Edge case this is good so I did my math wrong if x is actually equal to n then we probably don't want to execute the loop so I missed the edge case where they're actually equal unfortunate so we should probably change this to just a less than so now once they become equal or X exceeds n then we will return the comparison I actually coded it correctly the first time but always live demos are the worst but you can see this code does work and it is pretty efficient but if you read the description they actually ask us can you solve it without Loops or recursion and the easiest way to do that would just be with logarithms because if you know a logarithm is basically a way to get the exponent of a number so we would do log base 2 of N and we would check if it's a whole number not a decimal now internally that's pretty much doing a loop anyway so I'm actually going to show you a couple more interesting solutions to this problem so let's break it down for a second and think about the numbers 1 2 4 8 Etc if you are familiar with binary you know one in binary is just going to be a bunch of zeros and then a one two is going to be a bunch of zeros and a one Z four is going to be 1 0 0 8 is going to be 1 0 0 0 so to take a number and to multiply it by two just means to take this one and shift it to the left by one this is the one's place this is the two's place this is The Four's place this is the eights place this tells you how many eights we have and it just keeps going like that so one thing you can kind of tell from a power of two is that among all of the bits we don't really care how many there are or where they are among all of them there's only going to be a single one bit okay but knowing that how exactly does it help us well it's definitely not easy to come up with but the idea is that sort of the inverse of all of these bits like take the one and every bit to the right of it the inverse of that would look like this 0 1 1 1 1 and if we were able to get the inverse we know that all the rest of these bits are going to be zero there's just going to be a single one here if we can somehow get this inverse we know if we take these two numbers and do the bitwise and of that meaning for every pair of bits we take the and of them so these two anded together would be zero these two Ed together would be zero and these would be zero and zero as well basically both of the bits need to be one for us to get a one in the result otherwise we get a zero in the result now obviously you can see if we took this number and its inverse and we bitwise and them we're going to get zeros in all places so that's only going to be true when you have two inverse numbers now it just so happens that when you have a number with only a single one bit it's pretty easy to get the inverse of it all you have to do is subtract one when you have the number 1,000 like not the binary number when you have the number 1,000 subtract one and you get 999 similarly in binary subtract one from this you lose the most significant bit and then you get ones in the remaining position so we will easily be able to get this and easily be able to do the bitwise and if you were to try the exact same thing with a number that has two ones in it it wouldn't work subtract one from this number you're going to get these and you're still going to have a one over here so try doing the bitwise end of these two together yeah you'll have zeros all over here but you're going to end up with a one over here so the result is not going to be zero this only works with numbers that have a single one bit this is not a solution that's easy to reason about but once you have figured it out it's pretty easy to code one thing with this solution we will have to still verify that n is greater than zero strictly greater so coding this solution is pretty easy all we do Check N is greater than zero and logic and and then here we take n and then bitwise and it with the ersan sign and then do nus1 and so if this itself is equal to zero then we know that n Only Had a single one bit so let's run this and as you can see on the left it works it's pretty efficient in terms of Big O time complexity though it's not really any more efficient than the previous solution and technically the previous solution since the number was up to 2 ^ of 32 the previous solution was constant time but what if that boundary was not given to us what if n could be arbitrarily large then our previous solution with the loop is technically log base 2 of n it's a log n solution if this number can grow infinitely large but this solution here is theore theoretically a constant time solution a true constant time solution but not practically speaking because numbers are usually stored in 32 bits or 64 bits like there is a limit and if you want numbers bigger than that there is some kind of wrapper class around that that's what python does I think even this solution theoretically is a lend solution so one last solution I want to show you and this solution is definitely more up my alley this is more of a true math solution if you notice something about any number 2 to the^ of x if you were to take the prime factorization of that number what are all the factors of that number well we for sure know 2 * 2 * 2 creates that number this can't be split it is a prime number take the prime factorization of this and this is the only thing you're going to get you're not going to get a three in there you're not it's theoretically impossible for three to be a factor of this number it's impossible you might get 2 * 4 you might get 2 * 8 and this will turn into that number but notice these are not prime numbers these are not prime factors these are also reduced to this 222 and I'm probably missing one more two for this eight but that's the idea you might not remember this from your high school math or whatever prime factors is what can allow us to solve the problem now that you know this how can you use this knowledge to solve this problem well basically what we're saying is that if the number given to us n is truly a power of two then we should be able to take another value that's a power of two that is technically greater than or equal to n and if we were to take them and divide them take this and divide it by n which is the given value the result should be an integer now the only question is how do we get a number that is for sure greater than or equal to n well basically we get the largest power of two that is available to us and you might think it's 2 to the^ of 32 based on what I said earlier but technically 32bit integers go up until -2 to ^ 32 all the way up until 2 ^ of 31 minus1 and the reason for that is because you do have to remember zero is included in that and I actually think I have this wrong this should actually be to the power of 31 because I was going to say a 32bit integer can only store this many possible values where the most significant bit is usually used for the sign for negative or positive we won't go into that so basically what I'm saying is the largest possible power of two that we have is going to be 2 to the power of 31 or actually I'm messing this up this is the biggest number we can possibly have so really the biggest power of two is 2 the^ of 30 so this is enough information for us to be able to solve it the math way we'll first get this number which is going to be 2 ^ of 30 and then we'll mod it by n and make sure that the remainder is equal to zero so that we know for sure that this is a whole number okay so finishing up let's check n is greater than zero and for sure that number 2 to the power of 30 moded by n is equal to zero now how do you get 2 the Power of 30 this is one way to to do it we could also take one and shift it to the left 30 times and the reason we shift it 30 times is because technically the number one itself is equal to 2 to the power of 0 and if we want 2 the Power of 30 we take one and shift it to the left 30 times so that is the math behind that now let's just run it okay it looks like this is wrong but I'm pretty sure we just forgot to put the parentheses around here yep uh that was right so we just needed to add those parentheses really sorry about that mistake I've been a little sloppy today but you can see that this solution also works and it's pretty efficient if you're preparing for coding interviews check out n code. thanks for watching and I'll see you soon