class Solution:
    def nthUglyNumber(self, n: int) -> int:

        # ugly numbers are represented by
        # ugly = (2**x)(3**y)(5**y)
        prev_mult_of_2_index = 0
        prev_mult_of_3_index = 0
        prev_mult_of_5_index = 0
        uglys = []
        uglys.append(1)


        for i in range(n-1):

            # next multiple of 2 = 2*(previous multiple of 2)
            # next multiple of 3 and next multiple of 5 likewise
            # So the idea is that we are trying to record which one was
            # the last multiple of 2, 3 and 5
            next_multiple_of_2 = uglys[prev_mult_of_2_index]*2
            next_multiple_of_3 = uglys[prev_mult_of_3_index]*3
            next_multiple_of_5 = uglys[prev_mult_of_5_index]*5

            min_ugly = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)
            uglys.append(min_ugly)

            if min_ugly == next_multiple_of_2:
                prev_mult_of_2_index += 1

            if min_ugly == next_multiple_of_3:
                prev_mult_of_3_index += 1

            if min_ugly == next_multiple_of_5:
                prev_mult_of_5_index += 1

        return uglys[n-1]