[LeetCode with Python] 264. Ugly Number II

Difficulty : Medium

1st Approach : search all postive numbers and check if they are ugly -> Time Limit Exceeded!

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        uglies = [0] * (n + 1)
        i = 0
        num = 1
        while i < n + 1:
            origin_num = num

            while not num % 5:
                num //= 5

            while not num % 3:
                num //= 3

            while not num % 2:
                num //= 2

            if num == 1:
                uglies[i] = origin_num
                i += 1
                # print(uglies)
            num = origin_num + 1

        return uglies[n - 1]

2nd Approach : (reference from http://www.leetcode-solution.com/2019/06/01/0264-ugly-number-ii.html)
Just search multiples of 2, 3, 5. Use 3 indeces one of which matches to 2, 3, 5 one by one. When common multiple comes out, increase all divisors' indices.

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        nums = []
        idx_2, idx_3, idx_5 = 0, 0, 0
        nums.append(1)
        for i in range(1, n):
            min_value = min(2 * nums[idx_2], min(3 * nums[idx_3], 5 * nums[idx_5]))
            if min_value == 2 * nums[idx_2]:
                idx_2 += 1
            elif min_value == 3 * nums[idx_3]:
                idx_3 += 1
            else:
                idx_5 += 1
            nums.append(min_value)
        return nums[n - 1]