Python solution which runs O(n) that beats 92.67%.


  • 0
    M
        def nthUglyNumber(self, n):
            i2, i3, i5 = 0, 0, 0
            nextMultiOf2 = 2
            nextMultiOf3 = 3
            nextMultiOf5 = 5
            ugly = [1]
            for i in xrange(n):
                nextNumberToAdd = min(nextMultiOf2, nextMultiOf3, nextMultiOf5)
                ugly.append(nextNumberToAdd)
                if nextNumberToAdd == nextMultiOf2:
                    i2 += 1
                    nextMultiOf2 = ugly[i2] * 2
                if nextNumberToAdd == nextMultiOf3:
                    i3 += 1
                    nextMultiOf3 = ugly[i3] * 3
                if nextNumberToAdd == nextMultiOf5:
                    i5 += 1
                    nextMultiOf5 = ugly[i5] * 5
            return ugly[n-1]
    

Log in to reply
 

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