[LeetCode Road] Power of Two - Solution/C++

231. Power of Two

Question:

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^x.

Example:

Input: n = 1
Output: true
Explanation: 2⁰ = 1

Input: n = 16
Output: true
Explanation: 2⁴ = 16

Input: n = 3
Output: false

Input: n = 4
Output: false

Input: n = 5
Output: false

Constraints:

-2³¹ <= n <= 2³¹ - 1

Source code

Version 1

Idea:
It is an iterator method. For each loops, use % 2 to get a remainder, if a remainder is zero, n will be n / 2. Until n % 2 is not equal to zero, return n == 1.

Time complexity: O(logn)
Space complexity: O(1)

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;
        while(n % 2 == 0){
            n /= 2;
        }
        return n == 1;
    }
};

Version 2

Idea:
This is a bit operation. Let me take some examples of the power of 2:
n = 1 -> 00000001 (bit)
n = 2 -> 00000010 (bit)
n = 4 -> 00000100 (bit)
n = 8 -> 00001000 (bit)
   .
   .
   .
n = 128 -> 010000000 (bit)

If n - 1, most of bits change from 0 to 1 and there is one bit turn to 0.
Hence, & operation is a easy way to check whether it is the power of 2. If n is the power of 2, (n & (n - 1)) is 0.

Time complexity: O(1)
Space complexity: O(1)

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