LeetCode #231 Power of Two Solution & Explanation

LeetCode Problem

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.

Follow up: Could you solve it without loops/recursion?

Solution

We can solve this problem with a simple while loop.

However, it’s important to be mindful of the differences in division behavior among different programming languages. In languages like C# and Java, integer division will result in an integer, so we multiply the dividend by 1.0 to ensure it becomes a floating-point number.

And now, let’s consider the range of ‘power of two’ numbers.

First, power of two numbers are always non-negative, meaning they are greater than or equal to zero.

Second, in the context of this problem, we don’t need to consider fractional or non-integer values (e.g., 2^1/2). We are only interested in whole numbers that are powers of two, such as 2, 4, 8, 16, 32, etc.

C# Solution

⚠️Solution1 – using loop

public class Solution {
    public bool IsPowerOfTwo(int n) {
        if(n<0){
            return false;
        }

        double nn = n*1.0;
        while(nn>=2)
        {
            nn/=2;
        }
        return nn == 1.0;
    }
}

In the code, we use a ‘while’ loop to repeatedly divide the number ‘nn’ by 2.

This loop continues until ‘nn’ becomes less than 2. At this point, we know that if ‘nn’ is exactly 1.0, it means the original number ‘n’ is a power of two.

This is because 2⁰ equals 1, and any further division would result in a number less than 1, indicating that it’s not a power of two.

In the follow-up of the problem, it asks if we can solve it without using loops/recursion.

Now, we can examine the binary representations to identify powers of two and find their common properties.

• 2⁰=1 (binary: 1)
• 2¹=2 (binary: 10)
• 2²=4 (binary: 100)
• 2³=8 (binary: 1000)
• 2⁴=16 (binary: 10000)
• 2⁵=32 (binary: 100000)
• 2⁶=64 (binary: 1000000)
• 2⁷=128 (binary: 10000000)
• 2⁸=256 (binary: 100000000)
• 2⁹=512 (binary: 1000000000)
• 2¹⁰=1024 (binary: 10000000000)

We can observe that the powers of 2 have a pattern where they start with 1 followed by zeros.

⭐Solution2 – binary

public class Solution {
    public bool IsPowerOfTwo(int n) {
        if(n<0){
            return false;
        }
        string binaryStr = Convert.ToString(n, 2);
        return binaryStr.LastIndexOf('1') == 0;
    }
}

To determine if a number is a power of 2, we examine its binary representation. Since powers of 2 start with ‘1’ followed by zeros, we utilize the LastIndexOf method to check if the position of the ‘1’ is at index 0.

Java Solution

⚠️Solution1

class Solution {
    public boolean isPowerOfTwo(int n) {
        if(n<0){
            return false;
        }

        double nn = n*1.0;
        while(nn>=2)
        {
            nn/=2;
        }
        return nn == 1.0;
    }
}

⭐Solution2 – binary

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n < 0) {
            return false;
        }
        String binaryStr = Integer.toBinaryString(n);
        return binaryStr.lastIndexOf('1') == 0;
    }
}

You can refer to the explanation provided above for the C# version.

Python3 Solution

⚠️Solution1

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if(n<0):
            return False

        while(n>=2):
            n/=2

        return n == 1

⭐Solution2 – binary

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if(n<=0):
            return False

        s = "{0:b}".format(n)
        return s.rindex("1")==0

JavaScript Solution

⚠️Solution1

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function(n) {
    if(n<0){
        return false;
    }

    while(n>=2)
    {
        n/=2;
    }
    return n == 1;
};

Conclusion

We’ve solved this problem using a loop.

However, for the follow-up, there is certainly another solution. I’ll take some time to think about it, and I’ll update the post ASAP!

HAHA! Using binary makes it easy to solve! (updated)

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts or clicking ads, thanks you~~

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know !!

The problem link : Power of Two – LeetCode

Some Random Posts