LeetCode 342. Power of Four

Algorithm

LeetCode 342. Power of Four

쿠케캬캬 2023. 10. 23. 23:25

https://leetcode.com/problems/power-of-four/description

Power of Four - LeetCode

Can you solve this real interview question? Power of Four - 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: Input: n = 16 Outp

leetcode.com

비트 연산을 이용하면, 루프/재귀 없이 해결할 수 있었습니다.

n == 4^x라면, n > 0 이면서 짝수번째 비트가 1개만 켜져있어야합니다.

n & (n - 1) 가 0인지 확인하여 1개의 비트만 켜진지 확인해주고,

모든 짝수번째 비트가 켜진 mask와 & 연산하여 값이 있는지 확인해줍니다.

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