O(1) python solution with explanation

  • 8

    This solution should have been as simple as return math.log(n,3) % 1 == 0 ( %1 == 0 is to check the result of log is integer).

    However you will surprisingly find that the result of math.log(243, 3) is 4.999999999999999 instead of 5.0. This is not a bug: it’s a result of the fact that most decimal fractions can’t be represented exactly as a float. See Floating Point Arithmetic: Issues and Limitations for more information.

    So we need round() to approximate the result of log to nearest integer, and make sure the difference between the real value and rounded value is small.

    import math
    class Solution(object):
        def isPowerOfThree(self, n):
            :type n: int
            :rtype: bool
            if n < 1: return False
            x = math.log(n,3)
            return abs(round(x) - x) < 0.0000000000001

  • 0

    This solution failed with math.pow(3, 600).

  • 0

    I want to ask how do you determine the numbers of 0 in 0.0...01

  • 0

    You can estimate when the threshold will cause a problem by using $log(1+x) \approx x$ when x approaches zero.
    isPowerOfThree(3**28+1) returns True.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.