Recursion - Example

Recursion - Example

Leetcode 231 Power of Two

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

Constraints:

-2^31 <= n <= 2^31 - 1

Analysis:

One way is to think about this question recursively:

if n%2 == 1, then n must not be power of 2;

if not, then we just need to consider whether (n/2) is a power of 2 or not.

This is exactly the "same question with a smaller size"!

It is trivial to figure out the base cases:

if n == 0, return false;

if n == 1, return true.

See the code below:

class Solution {
public:
    bool isPowerOfTwo(int n) {
        // base cases
        if(n == 0) return false;
        if(n == 1) return true;
        // converging
        if(n%2 == 1) return false;
        return isPowerOfTwo(n/2);
    }
};

If interested, there are some other ways to solve this problem. For example, using bit manipulation, we can have the following solution:

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n-1)) == 0;
    }
};

Upper Layer