Teaching Kids Programming: Videos on Data Structures and Algorithms
Similar to Power of Three: Teaching Kids Programming – Algorithms to Check Integer Power of Three, we can check if the integer is power of two by using the following algorithms:
Recursive Algorithm to Check if Integer is Power of Two
1 2 3 4 5 6 7 | class Solution: def powerOfTwo(self, n): if n <= 0: return False if n == 1: return True return (n & 1) == 0 and self.powerOfTwo(n // 2) |
class Solution: def powerOfTwo(self, n): if n <= 0: return False if n == 1: return True return (n & 1) == 0 and self.powerOfTwo(n // 2)
Time complexity O(LogN) and Space complexity O(1) as the compiler may realize this is tail recursion and optimise it. Otherwise, the space complexity is O(LogN).
Iterative Algorithm to Multiple/Divide
Start from One, we can multiply by two until it is bigger or equal to N:
1 2 3 4 5 6 7 8 | class Solution: def powerOfTwo(self, n): if n <= 0: return False x = 1 while x < n: x <<= 1 return x == n |
class Solution: def powerOfTwo(self, n): if n <= 0: return False x = 1 while x < n: x <<= 1 return x == n
Or, we can divide by two (shift one to the right):
1 2 3 4 5 6 7 | class Solution: def powerOfTwo(self, n): if n <= 0: return False while (n & 1) == 0: n >>= 1 return n == 1 |
class Solution: def powerOfTwo(self, n): if n <= 0: return False while (n & 1) == 0: n >>= 1 return n == 1
Both have time complexity O(LogN). and Space complexity is O(1) constant.
Math Algorithm to Check if Power of Two
Let’s just check if the log(N) is integer:
1 2 3 4 5 6 | class Solution: def powerOfTwo(self, n): if n <= 0: return False x = log2(n) return int(x) == ceil(x) |
class Solution: def powerOfTwo(self, n): if n <= 0: return False x = log2(n) return int(x) == ceil(x)
The time complexity is almost O(1) constant as the log2 may be heavily optimised by hardware.
This also works, however the time complexity is O(logN) as the power computation is O(logN).
1 2 3 4 5 6 | class Solution: def powerOfTwo(self, n): if n <= 0: return False x = int(log2(n)) return 2**x == n # or pow(2, x) == n |
class Solution: def powerOfTwo(self, n): if n <= 0: return False x = int(log2(n)) return 2**x == n # or pow(2, x) == n
Binary Search Algorithm to Check if Power of Two
Of course, we can binary search the x where 2^x = n.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution: def powerOfTwo(self, n): if n <= 0: return False L, R = 0, n while L <= R: mid = (L + R) // 2 x = 2**mid if x == n: return True if x > n: R = mid - 1 else: L = mid + 1 return False |
class Solution: def powerOfTwo(self, n): if n <= 0: return False L, R = 0, n while L <= R: mid = (L + R) // 2 x = 2**mid if x == n: return True if x > n: R = mid - 1 else: L = mid + 1 return False
The time complexity is O(logN.LogN) because it takes O(LogN) to binary search and O(logN) to compute the power of two e.g. pow(2, mid). The space complexity is O(1) constant.
Bit Trick Algorithm to Check Integer Power of Two
If a integer is power of two, its binary will be a single 1 followed by zeros. Therefore, we can use the following one-liner to check if a integer is power of two in O(1) both time and space.
1 2 3 | class Solution: def solve(self, n): return (n > 0) and (n & (n - 1) == 0) |
class Solution: def solve(self, n): return (n > 0) and (n & (n - 1) == 0)
See also: C++ Coding Exercise – Check Integer Power of Two and Check Integer is the Power of Two
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Find Only Missing Number Between 0 and N
Next Post: Reverse a Sentence (Sentence Reversal Algorithm)