Leetcode – Power of Two Solution in Python

Spread the love

Introduction

The Power of Two problem is a common coding question found on LeetCode. In this article, we will explore the problem statement, analyze different approaches to solve this problem, and implement solutions in Python. We will also discuss time complexity, space complexity, and potential optimizations.

Problem Statement

The problem is as follows:

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.

Input

  • An integer n.

Output

  • A boolean value that indicates whether the given number is a power of two.

Approach 1: Logarithmic Approach

The first approach to solving this problem involves using logarithms. If n is a power of two, then log2(n) should be an integer. In other words, if n = 2^x, then log2(n) = log2(2^x) = x. If x is an integer, then n is a power of two.

import math

def isPowerOfTwo(n):
    # Check if n is less than or equal to 0
    if n <= 0:
        return False
    
    # Calculate log base 2 of n
    log_n = math.log2(n)
    
    # Check if log_n is an integer
    return log_n.is_integer()

Time Complexity

The time complexity of this approach is O(1) as the logarithm can be computed in constant time for an integer input.

Space Complexity

The space complexity is also O(1), since we are using a fixed amount of space to store the logarithm.

Approach 2: Bit Manipulation

Another approach to solving this problem involves using bit manipulation. An integer n is a power of two if it has exactly one bit set to 1 in its binary representation. This is because powers of two are represented as 1 followed by zeros in binary (1, 10, 100, …). We can use a trick to determine if a number has only one bit set: n & (n - 1) will be 0 if n is a power of two.

def isPowerOfTwo(n):
    # Check if n is less than or equal to 0
    if n <= 0:
        return False
    
    # Check if n has only one bit set to 1
    return n & (n - 1) == 0

Time Complexity

The time complexity of this approach is O(1), as bit manipulation is done in constant time.

Space Complexity

The space complexity is also O(1), as we are not using any additional space based on the input.

Approach 3: Iterative Division

Another approach to solving this problem is to continuously divide the number by 2 if it is divisible by 2 and check if we reach 1. If we reach 1, then it is a power of two, otherwise not.

def isPowerOfTwo(n):
    # Check if n is less than or equal to 0
    if n <= 0:
        return False
    
    # Continuously divide n by 2 and check if it reaches 1
    while n % 2 == 0:
        n = n / 2
        
    return n == 1

Time Complexity

The time complexity of this approach is O(log n) as we are dividing the number by 2 in each iteration.

Space Complexity

The space complexity is O(1), as we are only using a constant amount of space.

Performance Comparison and Analysis

The bit manipulation approach is generally the fastest and most efficient solution to this problem. The logarithmic approach is also efficient but may suffer from floating-point inaccuracies for very large values of n. The iterative division method is slower compared to the other two methods but is still a valid approach.

Conclusion

In this article, we dissected the Power of Two problem on LeetCode, investigated three distinct algorithms including logarithmic approach, bit manipulation, and iterative division, and implemented them in Python. Each approach has its own merits and demerits, and the bit manipulation method is often the most efficient. This problem is a good example of how a deep understanding of number theory and binary representations can lead to clever and efficient algorithms for seemingly simple problems.

Leave a Reply