720. Check if a Number is a Power of 2

Given an integer n, determine whether it is a power of 2. A positive integer is a power of 2 if there exists an integer k >= 0 such that n = 2^k. Return true if n is a power of 2, otherwise return false. Zero and negative numbers are NOT powers of 2. Implement the check recursively.

Input: A single integer n.

Output: Return a boolean: true or false (lowercase).

Examples

Input: 16
Output: true
Explanation: 16 = 2^4.

Input: 18
Output: false
Explanation: 18 is not a power of 2.

Input: 1
Output: true
Explanation: 1 = 2^0.

Constraints

• -10^9 <= n <= 10^9

Asked by