BinarySearch 0493 Ugly Number Sequel

Problem statement

https://binarysearch.com/problems/Ugly-Number-Sequel/

Solution

Equal to Leetcode 0264. Ugly Number II.

Complexity

Time and space is O(n).

Code

class Solution:
    def solve(self, n):
        factors, k = [2,3,5], 3
        starts, Numbers = [0] * k, [1]
        for i in range(n):
            candidates = [factors[i]*Numbers[starts[i]] for i in range(k)]
            new_num = min(candidates)
            Numbers.append(new_num)
            starts = [starts[i] + (candidates[i] == new_num) for i in range(k)]
        return Numbers[-1]