class Solution(object):
def nthUglyNumber(self, n):
"""
1, 2, 3, 4, 5, //6, 8, 9, 10, 12
the next ugly number is 6, how to find it? Intuitively , we multiply 2,3,5 to the ugly numbers appear before and find
a minimum number from the result as the new ugly number, but it would be O(n^2) time complexity
we set a counter for each prime factor and the counter is the index of dp, and we can take out a ugly number dp[counter] by counter,
then take min (dp[counter] * factor) as new ugly number , after that, update each counter if dp[counter] * factor equals to current ugly number
Update operation guarantees that , all (dp[counter] * factor) would more than the current ugly number
"""
dp = [1] * (n)
count2, count3, count5 = 0, 0, 0
for i in range(1,len(dp)):
cur_min = min([dp[count2]*2, dp[count3]*3, dp[count5]*5])
if cur_min == 14:
print(count2 ,count3, count5)
if dp[count2] * 2 == cur_min: count2 += 1
if dp[count3] * 3 == cur_min: count3 += 1
if dp[count5] * 5 == cur_min: count5 += 1
dp[i] = cur_min
return dp[-1]
