Power of Two Leetcode Solution

We are given an integer and the goal is to check whether the integer is a power of two, that is, it can be represented as some whole power of ‘2‘.

Example

16

Yes

13

No

Approach

A trivial solution can be: Check if all prime factors of the integer are all ‘2‘. The time complexity of this method would be O(log2N). In order to do it in an optimal way, we can take help of Bit manipulations.

“Any number which is a power of two can only have a single bit set in binary representation”

How can it be checked that there is only a single bit set in the binary form?

Consider any number, x.

Now, if x is some power of two, then (x – 1) will turn off all the right bits to the set bit(set them as ‘0’) and the set bit would be unset.

x = 8[1000], x – 1 = 7[0111]

So, using BITWISE-AND of x and (x – 1), we can say if a number is some power of two, then, x & (x – 1) = 0

Algorithm(Trivial)

1. Keep dividing the number by ‘2’ until it is not divisible by ‘2’ anymore.
2. If the number is equal to ‘1’:
   • The integer is a power of two
3. Else
   • The integer is not a power of two

Algorithm(Bit-Manipulation)

1. Check if x & (x – 1) is equal to zero
   • If yes, the number is a power of 2
   • The integer is not a power of 2, otherwise

Implementation

C++ Program of Power of Two Leetcode Solution

Naive Method

#include <bits/stdc++.h>
using namespace std;

bool powerOfTwo(int n)
{
    while(n % 2 == 0)
        n /= 2;
    return (n == 1);
}


int main()
{
    int n = 16;
    if(powerOfTwo(n))
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';


    return 0;
}

Optimal Method

#include <bits/stdc++.h>
using namespace std;

bool powerOfTwo(int n)
{
    //16 = [10000]
    //15 = [01111]
    //16 & 15 = 0
    return (n & (n - 1)) == 0;
}


int main()
{
    int n = 16;
    if(powerOfTwo(n))
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';


    return 0;
}

Yes

Java Program of Power of Two Leetcode Solution

Naive Method

class power_of_two
{
    public static boolean powerOfTwo(int n)
    {
        while(n % 2 == 0)
            n /= 2;
        return (n == 1);
    }

    public static void main(String args[])
    {
        int n = 16;
        if(powerOfTwo(n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Optimal Method

class power_of_two
{
    public static boolean powerOfTwo(int n)
    {
        return (n & (n - 1)) == 0;
    }

    public static void main(String args[])
    {
        int n = 16;
        if(powerOfTwo(n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Yes

Complexity Analysis

Time Complexity of Power of Two Leetcode Solution

The time complexity of Naive Approach is O(log2N), where N = given integer. However, the optimal approach is faster, as Bitwise-And is faster and therefore has a time complexity of O(1).

Space Complexity of Power of Two Leetcode Solution

Only space used in the program is the function signature. Therefore, constant space is used – O(1).