Solution for Leetcode 231

Hello, Welcome to my June Challenge of Problem Solving and finding solutions to Leetcode's Data Structures and Algorithm questions. Here, I choose a question daily and try to solve it, and finally pen down my process of flow in solving the question.

I hope you find it helpful. Today I will be solving Leetcode's question 231 - Power Of Two

Problem Statement

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<sup>x</sup>.

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

Thought Process/ Intuition

When initially approaching the problem of determining whether an integer is a power of two, several strategies come to mind:

1. Bit Manipulation: Powers of two have a distinctive pattern in binary representation. They have only one bit set to 1, and all other bits are 0. By checking if the given integer has exactly one bit set, we can determine if it is a power of two.

2. Mathematical Approach: Another approach involves utilizing mathematical properties of powers of two. We can calculate the logarithm base 2 of the given integer and check if it results in a whole number. If it does, then the integer is a power of two.

3. Iterative Division: We can repeatedly divide the given integer by 2 until it becomes 1 or an odd number. If it eventually becomes 1, then it is a power of two. Otherwise, it is not.

The Approach

Based on the above approach, I had three solutions for this problem

Solution 1 - Bit Manipulation

1. First, we check if n is less than or equal to 0. If it is, we immediately return False since powers of two are positive integers.

2. If n is greater than 0, we perform a bitwise AND operation between n and n - 1.

3. If the result of the bitwise AND operation is 0, it indicates that n is a power of two.

   • This is because a power of two in binary representation has only one bit set to 1, and subtracting 1 from a power of two results in a number with all lower bits set to 1. For example, 8 in binary is 1000, and 7 in binary is 0111.

   • When we perform the bitwise AND operation between 8 (1000) and 7 (0111), the result is 0.

   • In contrast, if n is not a power of two, the bitwise AND operation will yield a non-zero value.

4. If the result of the bitwise AND operation is not 0, it means that n is not a power of two, and we return False.

5. If the result of the bitwise AND operation is 0, we can conclude that n is a power of two, and we return True.

This approach utilizes the property that a power of two has a unique bit representation with only one bit set to 1, allowing us to detect if an integer is a power of two using a simple bitwise manipulation.

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

• The function is_power_of_two takes an integer n as a parameter.

• if n <= 0:: This condition checks if the given integer n is less than or equal to zero.

  • If n is less than or equal to zero, it means it cannot be a power of two since powers of two are positive integers. In such cases, the function immediately returns False.

• else:: If the condition in the if statement is not satisfied, i.e., n is greater than zero, the function proceeds to this else block.

• (n & (n - 1)) == 0: This expression checks whether n is a power of two by performing a bitwise AND operation between n and n - 1, and then comparing the result with 0.

  • (n - 1) subtracts 1 from n. Since n is assumed to be a power of two, subtracting 1 from it results in a number with all the lower bits set to 1. For example, if n = 8, then (n - 1) = 7, which is 111 in binary.

  • The bitwise AND operation n & (n - 1) compares the binary representation of n and (n - 1). If any bit is set to 1 in both numbers, the result will not be zero.

  • If the result of the bitwise AND operation is 0, it means that n is a power of two. This is because a power of two in binary representation only has a single bit set to 1, and subtracting 1 from a power of two results in a number with all lower bits set to 1. Therefore, the bitwise AND operation will yield 0.

• The function returns True if the result of the (n & (n - 1)) == 0 expression is True, indicating that n is a power of two. Otherwise, it returns False.

Solution 2 - Mathematical Approach

import math

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

        return power == int(power)

• The solution begins by checking if the given integer n is less than or equal to 0. If it is, we immediately return False since powers of two are positive integers.

• If n is greater than 0, we calculate the logarithm base 2 of n using the math.log2() function.

• The calculated power represents the exponent to which 2 must be raised to obtain n. For example, if n = 16, the calculated power would be 4 since 2 raised to the power of 4 is 16.

• We then check if power is equal to its integer counterpart int(power). If it is, it means that power is a whole number, indicating that n is a power of two.

• If power is not equal to its integer counterpart, it means that n is not a power of two, and we return False.

• If power is equal to its integer counterpart, we can conclude that n is a power of two, and we return True.

Solution 3 - Iterative Division

To solve the problem of checking if an integer n is a power of two using iterative division, we can follow the approach below:

1. First, we check if n is less than or equal to 0. If it is, we immediately return False since powers of two are positive integers.

2. While n is divisible by 2 (i.e., n % 2 == 0), we continuously divide n by 2.

   • This iterative division reduces n to half its value in each iteration.

3. After the loop ends, we check if the final value of n is equal to 1.

   • If n is equal to 1, it means that the original input n was a power of two, and we return True.

   • If n is not equal to 1, it indicates that the original n was not a power of two or it was not a positive integer, and we return False.

Here's the iterative implementation of the solution in Python:

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

        while n % 2 == 0:
            n //= 2

        return n == 1

Determining the most efficient method

1. Bit Manipulation Approach:

• Time Complexity: O(1)

  • The bit manipulation approach performs a constant number of operations regardless of the value of n. It only involves a bitwise AND operation and a comparison, which can be done in constant time.

• Space Complexity: O(1)

  • The bit manipulation approach does not require any additional space. It only uses a constant amount of space to store the intermediate results.

1. Mathematical Approach:

• Time Complexity: O(1)

  • The mathematical approach also performs a constant number of operations, such as calculating the logarithm and performing an equality check. These operations have constant time complexity.

• Space Complexity: O(1)

  • The mathematical approach does not require any additional space. It only uses a constant amount of space to store the intermediate results.

1. Iterative Division Approach:

• Time Complexity: O(log n)

  • The iterative division approach performs repeated divisions of n by 2 until it becomes 1 or an odd number. The number of divisions required is logarithmic in the value of n. Hence, the time complexity is O(log n).

• Space Complexity: O(1)

  • The iterative division approach does not require any additional space. It performs the division in place without using any additional data structures.

In terms of time complexity, both the bit manipulation approach and the mathematical approach have a constant time complexity of O(1). However, the bit manipulation approach is slightly more efficient as it involves fewer operations.

Overall, the bit manipulation approach stands out as the most efficient method in terms of both time and space complexity. It provides a concise solution that can determine if an integer is a power of two with a constant number of operations.