# Python O(logn) time recursion solution

• 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``````

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

• 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.

• 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``````

• 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.

• @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)
``````

• This post is deleted!

• 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

• time exceed isn't it???

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