My Solution To LeetCode 231: Power Of Two

The Problems

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 == 2x.

Example 1:

                  Input: n = 1
Output: true
Explanation:20 = 1
                

Example 2:

                  Input: n = 16
Output: true
Explanation:24 = 16
                

Example 3:

                  Input: n = 3
Output: false
                

Constraints:

• 231 <= n <= 231 - 1

Solution 1: Logarithms

You can use logarithms to solve this problem.

With this in mind, we can then come up with the solution below:

                  public class Solution {
    public bool IsPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        double logarit = Math.Log(n, 2);
        return Math.Abs(logarit - Math.Round(logarit)) < 1e-10;
    }
    
}
                

First, we reject all n that are zero or negative. Then, we find the log base 2 of n and round the exponent to the nearest whole number. Next, we’re going to check if the real exponent and the rounded one differ by almost nothing. If it is less then 1e - 10, then n is a power of 2.

Nevertheless, you should be cautious when doing it like this, as floating-point numbers can have rounding errors for large values of n. That’s why in competitive programming or coding interviews, the bitwise method below is preferred. It’s much more precise and much faster

Solution 2: Bitwise Method

In a bitwise operation, a positive integer is a power of two if and only if it has exactly one bit set in its binary representation. Which means that the AND operator of n and n - 1 will be 0.

Thus, the solution for the LeetCode problem can be as follows:

                  public class Solution {
    public bool IsPowerOfTwo(int n) {
        bool ans = false;
        if (n <= 0) {
            ans = false;
        } else if ( (n & (n - 1)) == 0) {
            ans = true;
        }

        return ans;
    }
    
}
                

This solution avoids floating-point calculations that might cause precision errors.

Read more at: Lazzerex’s Blog