Teaching Kids Programming – Algorithms of Power of Two

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) —