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


  • 0
    M

    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

  • 0

    I have the same question as yours.


  • 0
    M

    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]

Log in to reply
 

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