[LeetCode] 264. Ugly Number II

Problem : https://leetcode.com/problems/ugly-number-ii/

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        result = [1] * n
        
        l1 = l2 = l3 = 0
        i = 0
        
        for i in range(n-1):
            n1 = result[l1] * 2
            n2 = result[l2] * 3
            n3 = result[l3] * 5
            
            tmp = min(n1, n2, n3)
            if n1 == tmp:
                l1 += 1
            if n2 == tmp:
                l2 += 1
            if n3 == tmp:
                l3 += 1
        
            result[i+1] = tmp
        
        return result[-1]

An ugly number must be multiplied by either 2, 3, 5 from a smaller ugly number.

The smallest ugly number is 1. So starts from 1 and multiple to 2, 3, 5, then find the smallest as the next ugly number

A naive implementation.

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp2 = [2]
        dp3 = [3]
        dp5 = [5]
        
        i = j = k = 0

        x = 1
        
        for _ in range(1, n):
            mi = min(dp2[i], dp3[j], dp5[k])
                   
            if mi == dp2[i]:
                i += 1
                dp2.append(mi * 2)
                dp3.append(mi * 3)
                dp5.append(mi * 5)
            elif mi == dp3[j]:
                j += 1
                dp3.append(mi * 3)
                dp5.append(mi * 5)
            else:
                k += 1
                dp5.append(mi * 5)

            x = mi
            
        return x

Edited on 05/16/2021. Add the naive implementation.