Leetcode 231: powers of 2

In this Leetcode problem, we should return a boolean indicating if the integer n in input is a power of 2.

Problem statement

To do that, we want to divide the integer n by 2 until one of these conditions happen:

1. n is not divisible by 2, and n == 1, in which case n was a power of 2 at the beginning.
2. n is not divisible by 2, and n != 1, in which case n was not a power of 2 at the beginning.

This stems directly from the fact that n is a power of 2 if and only if

n = 2^p = 2 * 2 * ... * 2 (p times).

To implement it effectively, although the algorithm is naturally recursive, we introduce a while loop to use constant space, we use bit operation n >>= 1; to divide n by 2, but it is equivalent to n /= 2; (I don’t think the compiler makes a difference). Similarly there are 2 ways to check if n is divisible by 2: (n & 1) == 0 or n % 2 == 0.

I used the bit operations in each case, just to show some bit operations. Here is the full code:

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n == 0) {
            return false;
        }
        while ((n & 1) == 0) {
            n >>= 1;
        }
        return (n == 1);
    }
}

This one is a short one, in Leetcode test it beats 100% and runs in 1ms.

Happy coding!

Follow-up

• Checkout another post: Number of steps to reduce a number to 0
• Contact me: poitevinpm@gmail.com
• Looking to interview for a software engineer position? Contact me :)