# Why is my correct Python code for Ugly Numbers II getting Time Limit Exceeded?

• I have tested my code elsewhere and it's correct. But it's getting a Time Limit Exceeded. What am I doing wrong?

``````class Solution:
# @param {integer} n
# @return {integer}
def nthUglyNumber(self, n):
uglies = [1]

def findNextUgly(lowerUgly):
for ugly in uglies:
if ugly > lowerUgly:
return ugly
counter = 0
currentUgly = 1
while (counter < n):
counter+=1
currentUgly  = uglies[-1]
new2 = findNextUgly((currentUgly/2))*2
new3 = findNextUgly((currentUgly/3))*3
new5 = findNextUgly((currentUgly/5))*5
uglies.append(min(new2, new3, new5))
return currentUgly``````

• I have the same question as yours.

• The problem is in findNextUgly(). It's O(n) as it searches through all elements in uglies. I could use binary search or I could use a better solution:

``````    uglies = [1]
doubleLoc = 0
tripleLoc = 0
quintLoc = 0
for i in range(n-1):
# potential uglies
next2 = uglies[doubleLoc]*2
next3 = uglies[tripleLoc]*3
next5 = uglies[quintLoc]*5

# the nextUgly is the min of potentials
nextUgly = next2 if next2 < next3 else next3
nextUgly = next5 if next5 < nextUgly else nextUgly

# it could be possible that more than one
# option yields the nextUgly
if nextUgly == next2:
doubleLoc+=1
if nextUgly == next3:
tripleLoc+=1
if nextUgly == next5:
quintLoc+=1

uglies.append(nextUgly)
return uglies[-1]``````

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