Question

Formatted question description: https://leetcode.ca/all/342.html

 342	Power of Four

 Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

 Example:
 Given num = 16, return true.
 Given num = 5, return false.

 Follow up: Could you solve it without loops/recursion?

Algorithm

Diveded by 4

The most direct way is to keep dividing by 4 to see if the final result is 1.

Mast

First judge whether it is 2 to the Nth power: (num&(num-1)) == 0

Remove the number that is not 4 to the power of N

0x55555555 is to get rid of those power of 2 but not power of 4

so that the single 1 bit always appears at the odd position

The highest 1 of the power of 4 is the counting digit, then we only need to compare it with the previous number (0x55555555) <==> 1010101010101010101010101010101. If the number obtained is still itself, we can be sure that it is a power of 4

Math

After determining that it is a power of 2, I found that as long as it is a power of 4, it can be divisible by 3 after subtracting 1.

Code

Java

  • 
    public class Power_of_Four {
    
        class Solution_3 {
            public boolean isPowerOfFour(int num) {
                return num > 0 && !(num & (num - 1)) && (num - 1) % 3 == 0;
            }
        }
    
    
        class Solution_intuitive {
            public boolean isPowerOfFour(int num) {
                while (num && (num % 4 == 0)) {
                    num /= 4;
                }
                return num == 1;
            }
        }
    
    
        class Solution {
            public boolean isPowerOfFour(int num) {
    
                return num > 0 && (num&(num-1)) == 0 && (num & 0x55555555) != 0;
    
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/power-of-four/
    // Time: O(1)
    // Space: O(1)
    class Solution {
    public:
        bool isPowerOfFour(int num) {
            return __builtin_popcount(num) == 1 && ((~0x55555555 & num) == 0);
        }
    };
    
  • class Solution(object):
      def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return num & (num - 1) == 0 and (num - 1) % 3 == 0
    
    

All Problems

All Solutions