Documentation: Checking if a Number is a Power of Two

Problem Statement

The goal is to determine if a given integer ( n ) is a power of two. A number is a power of two if it can be expressed as ( 2^k ) where ( k ) is a non-negative integer. For example, ( 1 (2^0), 2 (2^1), 4 (2^2), 8 (2^3) ) are all powers of two.

Mathematical Background

A number ( n ) is a power of two if:

It is greater than zero.
It has exactly one bit set in its binary representation.

For example:

( 1 ) in binary is ( 0001 ) (which is ( 2^0 ))
( 2 ) in binary is ( 0010 ) (which is ( 2^1 ))
( 4 ) in binary is ( 0100 ) (which is ( 2^2 ))
( 8 ) in binary is ( 1000 ) (which is ( 2^3 ))

Key Properties

Divisibility by 2: A power of two can be divided by 2 repeatedly until it reaches 1.
Binary Representation: A power of two has only one '1' in its binary form.

Solution Overview

The solution involves checking if the number can be repeatedly divided by 2 until it reaches 1. If at any point the number is not divisible by 2, it is not a power of two.

Intuition Behind the Solution

Base Case: If ( n ) is less than or equal to 0, it cannot be a power of two.
Divisibility Check: A power of two will always be divisible by 2 until it reaches 1. If we encounter a remainder when dividing by 2, it indicates that the number is not a power of two.
Loop Until 1: We keep dividing ( n ) by 2 until it either becomes 1 (indicating it is a power of two) or we find it is not divisible by 2.

Step-by-Step Explanation of the Code

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n < 1) // Step 1: Check if n is less than 1
            return 0; // If true, return false (0)

        while (n != 1) { // Step 2: Loop until n becomes 1
            if (n % 2 != 0) // Step 3: Check if n is not divisible by 2
                return 0; // If true, return false (0)
            n /= 2; // Step 4: Divide n by 2
        }

        return 1; // Step 5: If we reach here, n is a power of two, return true (1)
    }
};

Code Breakdown

Line 1-2: Define the class Solution and the public method isPowerOfTwo that takes an integer ( n ).
Line 3: Check if ( n ) is less than 1. If it is, return 0 (false).
- Mathematical Calculation: If ( n < 1 ), then ( n ) cannot be expressed as ( 2^k ) for any non-negative integer ( k ).
Line 5: Start a while loop that continues until ( n ) equals 1.
Line 6: Inside the loop, check if ( n ) is not divisible by 2. If it is not, return 0 (false).
- Mathematical Calculation: If ( n \mod 2 \neq 0 ), then ( n ) is not a power of two.
Line 7: If ( n ) is divisible by 2, divide ( n ) by 2.
- Mathematical Calculation: ( n = n / 2 )
Line 9: If the loop completes and ( n ) equals 1, return 1 (true).
- Mathematical Calculation: If ( n ) reaches 1, it confirms that ( n ) was a power of two.

Example Walkthrough

Let's consider ( n = 8 ):

Initial Check: ( n = 8 ) (greater than 1, continue).
First Iteration: ( 8 \mod 2 = 0 ) (divisible by 2).
- Update ( n = 8 / 2 = 4 ).
Second Iteration: ( 4 \mod 2 = 0 ) (divisible by 2).
- Update ( n = 4 / 2 = 2 ).
Third Iteration: ( 2 \mod 2 = 0 ) (divisible by 2).
- Update ( n = 2 / 2 = 1 ).
Final Check: ( n = 1 ) (return true).

Complexity Analysis

Time Complexity: ( O(\log n) ) because we are dividing ( n ) by 2 in each iteration. The number of times we can divide ( n ) by 2 until we reach 1 is logarithmic in relation to ( n ).
Space Complexity: ( O(1) ) as we are using a constant amount of space.

Conclusion

This method efficiently checks if a number is a power of two by leveraging the properties of binary numbers and divisibility. The approach is straightforward and can be easily implemented in various programming languages. The detailed breakdown of each step and mathematical calculations provides a comprehensive understanding of the solution.

ALTERNATIVE APPROACHES: CHECK OUT THE NEXT POST

Solution with Explanation: Leetcode 231- Power of Two