Python O(logn) time recursion solution


  • 0
    D

    It has been run 4 times, the best time is 48ms 98.15%

    class Solution(object):
        def isUgly(self, num):
            """
            :type num: int
            :rtype: bool
            """
            # Base situation
            if num < 1:
                return False
            if num in (1,2,3,5):
                return True
            # Recursion
            q5, r5 = divmod(num,5)
            if r5 == 0:
                return self.isUgly(q5)
            else:
                q3, r3 = divmod(num,3)
                if r3 == 0:
                    return self.isUgly(q3)
                else:
                    q2, r2 = divmod(num , 2)
                    if r2 == 0:
                        return self.isUgly(q2)
                    else:
                        return False

  • 0
    W

    I don't think this is log(n).


  • 0
    D

    Well, the num is kept being divided by 5,3 or 2. The worst case happens when num is 2**N (pow of two). In the worst case, the program runs N round and every round is O(1). So it is log(n) even in the worst case.


  • 0
    C

    You can save the space of the recursive call stack by doing this:

    class Solution(object):
        def isUgly(self, num):
            """
            :type num: int
            :rtype: bool
            """
            
            while num % 2 == 0 and num!=0:
                num = num/2
                
            while num % 3 == 0 and num!=0:
                num = num/3
                
            while num % 5 == 0 and num!=0:
                num = num/5
            
            if num != 1:
                return False
            
            return True

  • 0
    D

    Thanks, you are right, and based on your solution, I made a little change and get about 5% speed gain. You can see the other answer.


  • 0
    D

    @coffeeaddict8 I modified your solution. And it looks a little simpler and runs a bit faster.

    def isUgly(self, num):
        if not num:
            return False
        else:
            while not num % 5: num /= 5
            while not num % 3: num /= 3
            while not num % 2: num /= 2
        return num == 1
    

    Using the following script, you can compare the speed of the two code.

    from timeit import timeit
    r,n = xrange(1000000),10
    class Solution(object):
        def isUgly1(self, num):
            while num % 2 == 0 and num!=0:
                num = num/2
            while num % 3 == 0 and num!=0:
                num = num/3
            while num % 5 == 0 and num!=0:
                num = num/5
            if num != 1:
                return False
            return True
        def isUgly2(self, num):
            if not num:
                return False
            else:
                while not num % 5: num /= 5
                while not num % 3: num /= 3
                while not num % 2: num /= 2
            return num == 1
        
    print timeit(lambda: map(Solution().isUgly1, r), number=n)
    print timeit(lambda: map(Solution().isUgly2, r), number=n)
    

  • 0
    C
    This post is deleted!

  • 0
    C

    Yes. Another optimization could be to return False for anything < 0 since OJ seems to consider -1 as a factor for all negative numbers. The solution I submitted to OJ contained optimization for <0


  • 0
    B

    time exceed isn't it???


Log in to reply
 

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