Leetcode – Power of Four Solution in Python

Spread the love

In this elaborate article, we will deeply analyze a well-known problem on LeetCode called the ‘Power of Four’. This problem is significant for understanding bitwise operations and mathematical properties. We will dissect the problem statement, and explore multiple approaches to solve this problem, evaluating their respective time and space complexities.

Introduction

Let’s start with the problem statement:

Given an integer n, return True if it is a power of four. Otherwise, return False.

Example:

Input: n = 16

Output: True

Explanation: 16 is 4^2, hence it is a power of four.

Understanding the Problem

The problem is fairly straightforward: we need to determine if the given integer n is a power of four. Specifically, we need to check if there exists an integer x such that 4^x = n.

Approach 1: Loop Iteration

A basic approach is to keep dividing the number by four and check if we can reach 1.

  1. If n is less than 1, return False.
  2. While n is greater than 1, check if n is divisible by 4. If it is, divide n by 4; otherwise, return False.
  3. If the loop ends, return True.
def isPowerOfFour(n):
    if n < 1:
        return False
        
    while n > 1:
        if n % 4 != 0:
            return False
        n /= 4
        
    return True

Time Complexity:

O(log₄n) – In the worst case, we keep dividing the number by 4 until we reach 1.

Space Complexity:

O(1) – We are not using any additional data structures.

Approach 2: Logarithm

We can also solve this problem using logarithms. If n is a power of four, then log₄(n) must be an integer. We can calculate the base 4 logarithm by using the change of base formula: log₄(n) = log₂(n) / log₂(4).

  1. If n is less than 1, return False.
  2. Calculate log₄(n) using the change of base formula.
  3. Check if log₄(n) is an integer. If it is, return True; otherwise, return False.
import math

def isPowerOfFour(n):
    if n < 1:
        return False
    
    log4_n = math.log2(n) / math.log2(4)
    return math.isclose(log4_n, round(log4_n))

Time Complexity:

O(1) – We perform a constant number of operations.

Space Complexity:

O(1) – No additional space is required.

Approach 3: Bit Manipulation

We can utilize bit manipulation for an optimized solution. If n is a power of four, its binary representation has only one ‘1’ bit, and the number of ‘0’ bits after the ‘1’ bit is even. For example, 4 is 100, 16 is 10000, and so on.

  1. Check if n has only one ‘1’ bit by using n & (n-1) == 0.
  2. Check if the number of ‘0’ bits after the ‘1’ bit is even by using n & 0xAAAAAAAA == 0.
def isPowerOfFour(n):
    return n > 0 and n & (n-1) == 0 and n & 0xAAAAAAAA == 0

Time Complexity:

O(1) – We perform bitwise operations that take constant time.

Space Complexity:

O(1) – No additional space is used.

Conclusion:

The ‘Power of Four’ problem on LeetCode demonstrates how mathematical insights and bitwise manipulation can be employed to devise efficient algorithms for seemingly simple problems. Through various approaches, ranging from basic loops and logarithmic calculations to sophisticated bitwise operations, this problem teaches the importance of evaluating different strategies to solve a given problem. It underlines the importance of understanding binary representations and mathematical properties, which can be crucial in optimizing algorithms for performance-sensitive applications. In coding interviews and real-world applications, being proficient in these concepts can prove to be invaluable.

Leave a Reply