Python solution using dp.


  • 0
    C

    Based on the discussion on StackOverFlow (http://stackoverflow.com/questions/4600048/nth-ugly-number).

    # dynamic programming
    def nthUglyNumber(self, n):
        ugly = [0] * n
        nxt = ugly[0] = 1
        i2 = i3 = i5 = 0
        nxt2, nxt3, nxt5 = ugly[i2]*2, ugly[i3]*3, ugly[i5]*5
        for i in xrange(1, n):
            nxt = min(nxt2, nxt3, nxt5)
            ugly[i] = nxt
            if nxt == nxt2:
                i2 += 1
                nxt2 = ugly[i2]*2
            if nxt == nxt3:
                i3 += 1
                nxt3 = ugly[i3]*3
            if nxt == nxt5:
                i5 += 1
                nxt5 = ugly[i5]*5
        return nxt # ugly[-1]

  • 0
    C

    A shorter version which is easier to understand:

     def nthUglyNumber(self, n):
        if n <= 0:
            return 0
        ugly = [1] * n
        i2 = i3 = i5 = 0
        for i in xrange(1, n):
            ugly[i] = min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
            if ugly[i] == ugly[i2]*2:
                i2 += 1
            if ugly[i] == ugly[i3]*3:
                i3 += 1
            if ugly[i] == ugly[i5]*5:
                i5 += 1
        return ugly[-1]

Log in to reply
 

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