326.Power of Three

Tags: [math]

Link: https://leetcode.com/problems/power-of-three/#/solutions

Given an integer, write a function to determine if it is a power of three.

Follow up:
Could you do it without using any loop / recursion?

Solution: Iteration

class Solution(object):
    def isPowerOfThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 0:
            return False

        exp = 0
        while 3 ** exp <= n:
            if 3 ** exp == n:
                return True
            exp += 1

        return False

Note:

• Time complexity = O(log(n), base=3), n is the given number.

Follow-up Solution: Math

class Solution(object):
    def isPowerOfThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 0:
            return False

        max_num_power_of_three = (int)(pow(3, (int)(math.log(0x7FFFFFFF) / math.log(3))))
        return max_num_power_of_three % n == 0

Revelation:

• 0x7FFFFFFF is the max int (32 bits int).
• First find the max int of the power of three, then check whether this max int (power of three) is multiple of the given n.
• When n is prime, the above algorithm is correct, but when n is composite number, the above algorithm doesn't work correctly.

Note:

• Time complexity = O(1).

Question:

• Why the above algorithm is correct? Why when n is not prime the above algorithm doesn't work correctly?