Ugly Number II LeetCode Solution

Quoestion: Click Here

If we pick a naive approach we will end up getting time exceeded error.So,we will solve this problem more efficiently Using Dynamic Programming

Algorithm:

1.Intialize an array result of size n

2.Update result[0] = 1

3.Intialize pointers p2,p3 and p5 to 0 (pointer for value 2,3 and 5)

4.Loop from i:1 to N

    =>find the minimum of three value (2*result[p2],3*result[p3] and          5*result[p5])

    =>put the value at the index i

    =>if minimum = 2*result[p2], then increment p2.

    =>if minimum = 3*result[p3], then increment p3.

    =>if minimum = 5*result[p5], then increment p5.

5.return last value of result array.

Python Code:

class Solution(object):

    

    def nthUglyNumber(self, n):

        res = []

        res.append(1)

        p2 = 0

        p3 = 0

        p5 = 0

        for i in range(1,n+1):

            minimum = min(res[p2]*2,res[p3]*3,res[p5]*5)

            res.append(minimum)

            if minimum == res[p2]*2:p2+=1

            if minimum == res[p3]*3:p3+=1

            if minimum == res[p5]*5:p5+=1

        

        return res[n-1]

Try Problem In LeetCode