342. Power of Four

Problem

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

Example 1:

Input: 16
Output: true

Example 2:

Input: 5
Output: false

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

Problem Summary

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

Solution Ideas

• Determine whether a number is the nth power of 4.
• The simplest idea for this problem is to use a loop, which can pass. But the problem asks for a way to determine it without loops, which requires using number theory.
• Prove that (4^n - 1) % 3 == 0: (1) 4^n - 1 = (2^n + 1) * (2^n - 1) (2) Among any 3 consecutive numbers (2^n-1), (2^n), (2^n+1), there must be one number that is a multiple of 3. (2^n) is definitely not a multiple of 3, so either (2^n-1) or (2^n+1) must be a multiple of 3. Therefore, 4^n-1 must be a multiple of 3.

Code

package leetcode

// Solution 1: Number theory
func isPowerOfFour(num int) bool {
	return num > 0 && (num&(num-1)) == 0 && (num-1)%3 == 0
}

// Solution 2: Loop
func isPowerOfFour1(num int) bool {
	for num >= 4 {
		if num%4 == 0 {
			num = num / 4
		} else {
			return false
		}
	}
	return num == 1
}