Power of Four | LeetCode 342 | C

2023-09-12
#LeetCode #C #Math #Bit Manipulation #Recursion
LeetCode

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4x.

Example 1:

1
2
Input: n = 16
Output: true

Example 2:

1
2
Input: n = 5
Output: false

Example 3:

1
2
Input: n = 1
Output: true

Constraints:

1
-231 <= n <= 231 - 1

Approach

1
2
If an integer is a power of four, only one bit is 1, others will be 0.
If an integer is a power of four, the only one bit is an even bit.

Algorithm

1
Check if the bit is an even bit and make sure only one bit is 1.

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isPowerOfFour(int n){
    int shift = 0, bit = 0, count =0;
    while(n>0)
    {
        bit = n&1;
        if(bit){
            count++;
            if(shift%2!=0)
                return false;
            if(count!=1)
                return false;
        }
        n>>=1;
        shift++;
    }
    return ((shift-1)%2==0)?true:false;
}