Power Of Two

                                            
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        return (n & (n - 1)) == 0;
    }
};

                                            
class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

                                            
class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 0:
            return False
        return n & (n - 1) == 0

                                            
bool isPowerOfTwo(int n) {
    if (n <= 0) {
        return false;
    }
    return (n & (n - 1)) == 0;
}

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

                                            
/**
 * @param {number} n
 * @return {boolean}
 */
const isPowerOfTwo = (n) => {
    return n > 0 && (n & (n - 1)) === 0;
};

                                            
function isPowerOfTwo(n: number): boolean {
    return n > 0 && (n & (n - 1)) === 0;
};

                                            
class Solution {
    /**
     * @param Integer $n
     */
    function isPowerOfTwo($n) {
        return $n > 0 && ($n & ($n - 1)) == 0;
    }
}

                                            
class Solution {
    func isPowerOfTwo(_ n: Int) -> Bool {
        return n > 0 && (n & (n - 1)) == 0
    }
}

                                            
class Solution {
    fun isPowerOfTwo(n: Int): Boolean {
        if (n <= 0) return false
        return n and (n - 1) == 0
    }
}

                                            
class Solution {
  bool isPowerOfTwo(int n) {
      return n > 0 && (n & (n - 1)) == 0;
      }
}

                                            
func isPowerOfTwo(n int) bool {
    return n > 0 && n&(n-1) == 0
}

                                            
# @param {Integer} n
# @return {Boolean}
def is_power_of_two(n)
    n > 0 && (n & (n - 1)) == 0
end

                                            
object Solution {
    def isPowerOfTwo(n: Int): Boolean = {
        n > 0 && (n & (n - 1)) == 0
    }
}

                                            
impl Solution {
    pub fn is_power_of_two(n: i32) -> bool {
        if n <= 0 {
            return false;
        }
        
        n & (n - 1) == 0
    }
}

                                            
-spec is_power_of_two(N :: integer()) -> boolean().
is_power_of_two(N) ->
    if
        N =:= 0 -> false;
        N band (N - 1) =:= 0 -> true;
        true -> false
    end.

To solve this coding challenge, you need to determine if a given integer \( n \) is a power of two. A number is considered a power of two if it can be expressed as \( 2^x \) where \( x \) is a non-negative integer. For example, 1, 2, 4, 8, and 16 are all powers of two.

Explanation

There are various methods to determine if a number is a power of two, ranging from loops and recursion to bit manipulation. The goal here is to efficiently check if \( n \) is a power of two without using loops or recursion. By leveraging bitwise operations, we can achieve this efficiently.

Key Insight:

A number \( n \) is a power of two if only one bit is set in its binary representation. For example:

\( 1 \) (binary
0001

)
\( 2 \) (binary
0010

)
\( 4 \) (binary
0100

)

In contrast, a number that is not a power of two will have more than one bit set in its binary representation. The critical observation for an efficient solution is this: for a number that is a power of two, \( n \& (n - 1) \) will be \( 0 \). This is because:

\( n \) (which is a power of two) has a single bit set.
\( n-1 \) will have all bits set to the right of the single bit set in \( n \).

For example:

\( n = 4 \) (binary
0100

)
\( n - 1 = 3 \) (binary
0011

)
\( 4 \& 3 = 0 \)

Step-by-Step Explanation

Check for zero or negative numbers early : If \( n \) is less than or equal to zero, it cannot be a power of two.
Bitwise Check : Use the bitwise operation \( n \& (n - 1) \). If the result is zero, then \( n \) is a power of two.

Pseudocode Explanation:

The pseudocode checks if the number is greater than zero and applies the bitwise check. This provides a clear and efficient method to determine if \( n \) is a power of two.

                                            
// Define a function that accepts an integer n
function isPowerOfTwo(n)
// If the number is less than or equal to zero, it cannot be a power of two
if n <= 0
return false

// Return true if bitwise AND of n and (n - 1) is zero
// This ensures only one bit is set in n
return (n AND (n - 1)) == 0

Detailed Steps in Pseudocode

Define the Function :

Name:
isPowerOfTwo
Input: Integer \( n \)

Early Exit for Non-Positive Numbers :

If \( n \) is lesser than or equal to zero, return
false

.

Bitwise Operation :

Perform the bitwise operation \( n \& (n - 1) \).
If the result of \( n \& (n - 1) \) is zero, return
true

, indicating \( n \) is a power of two.
Otherwise, return
false

.

This method eliminates the need for loops or recursion and provides an O(1) complexity solution, making it highly efficient.