231. Power of Two.cpp

/*
Given an integer, write a function to determine if it is a power of two.

Example 1:

Input: 1
Output: true
Explanation: 20 = 1
Example 2:

Input: 16
Output: true
Explanation: 24 = 16
Example 3:

Input: 218
Output: false


Solution one is recursive, solution two is using bit calculation
*/
//O(N)
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if ( n == 1 ) return true;
        if ( n % 2 != 0 || n == 0 ) return false;
        return isPowerOfTwo( n / 2 );
    }
};

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