Trying to Solve LeetCode power of 4 using recursion in Python

Question

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 == 4ˣ.

class Solution(object):
    def isPowerOfFour(self, n, count = 1):
        """
        :type n: int
        :rtype: bool
        """
        if n == 4:
            return True
        if n > 4:
            return self.isPowerOfFour(pow(n,1/count),count + 1)

I keep getting False as an output

Answer 1

If I pass an input that's less than 4, e.g. 2, your function will return None. I'm not sure why you say that the function returns False, but I think that might just be some quirk in LeetCode's testing infrastructure.

Anyway, to solve this problem using recursion, we make three observations:

1. 1 is a power of 4.
2. For n > 1, if n can be expressed as 4^x for some integer x, then so can n // 4 (as it would be equivalent to 4^(x - 1)).
3. If a number isn't divisible by 4 and is greater than 1, it isn't a power of 4.

This gives us the following recursive solution:

class Solution(object):
    def isPowerOfFour(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n == 1:
            return True
        elif n % 4 != 0:
            return False
        return self.isPowerOfFour(n // 4)