Welcome back to yet another tutorial of the series "recursion". Now that you have a idea of what recursion is, lets dive deep into solving some easy problems of leetcode on this particular topic.

Leetcode problem number 231

Problem statement:

Given an integer n, return true if it is a power of two. Otherwise, return false. An integer n is a power of two, if there exists an integer x such that n == 2^x.

Output format:

True or False

Thought process:

So, the key to solve any problem is to break it down in small parts.

There are three possibilities for n:

1. Odd
2. Even
3. Zero

Now, lets observe the pattern for each of the three cases. Let's take n= 13. No matter what will be the value of x (even, odd or zero), 2^x will always yield an even number (Except when x=0 and n = 1)

2^0 = 1

2^1 = 2

2^2 = 4

2^3 = 8 .......and so on

Clearly, any number n which is odd (other than '1'), cannot be a power of 2. To write it in terms of a simple code:

#if n is 1
if n == 1:
    return True
#checking if n is even
if n % 2 != 0:
    return False

Let's now move on to the second case, when n is even. Take n = 16. Since it is relatively a smaller number we know that for x = 4, n can be written as a power of two: 2^4 = 16. But this is not true for all even numbers.

One's digit of any number which can be written as power of 2 forms a pattern:

2^1 = 2

2^2 = 4

2^3 = 8

2^4 = 16

2^5 = 32

The pattern is 2, 4, 8, 6... If an even number has '0' at one's digit it will not be a power of 2. For n = 20:

20/2 = 10

10/2 = 5 ---> It gives us an odd number, so we can directly use information from our first case of odd number and return False!

If we see the pattern for n, where one's digit is 2,4,8,6:

16/2 = 8

8/2 = 4

4/2 = 2

2/2 = 1 --> we will reach 1 at the end.

So, now we know for any number to be written as a power of 2 it should yield 1 at the very end, after consecutive division by 2. Even if n = 1, we can write it as : 2^0 = 1 Our base case will be:

if n == 1:
   return True

To write whatever we have now, in terms of code:

def powerofTwo(n):
    if n == 1:
        return True
    if n % 2 != 0:
        return False
else:
    return powerofTwo(n//2)

Now, we are left with the last case, which is n = 0. when n is 0, clearly it cannot be written as a power of 2. The least number which can be written as power of any number is '1'. The final piece of our code will look something like:

def powerofTwo(n):
    if n == 1:
        return True
    if n % 2 != 0 or n == 0:
        return False
else:
    return powerofTwo(n//2)

That's it! If you have any suggestions, reach out to me at: tanishkaashi567@gmail.com

Follow me on github for more: Github