-
Notifications
You must be signed in to change notification settings - Fork 0
/
UglyNumber.py
56 lines (44 loc) · 1.09 KB
/
UglyNumber.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def maxDivide(a,b):
while a % b == 0:
a = a / b
return a
def isUgly(no):
no = maxDivide(no,2)
no = maxDivide(no,3)
no = maxDivide(no,5)
return 1 if no == 1 else 0
def getNthUglyNo(n):
i = 1
count = 1
while n > count:
i += 1
if isUgly(i):
count += 1
return i
no = getNthUglyNo(150)
print("150th ugly no. is ", no)
# Using Dynamic Programming
def getNthUglyNo(n):
ugly = [0]
ugly[0] = 1
i2 = i3 = i5 = 0
next_multiple_of_2 = 2
next_multiple_of_3 = 3
next_multiple_of_5 = 5
for z in range(1,n):
ugly[1] = min(next_multiple_of_2,next_multiple_of_3,next_multiple_of_5)
if ugly[1] == next_multiple_of_2:
i2 += z
next_multiple_of_2 = ugly[i2]*2
if ugly[1] == next_multiple_of_3:
i3 += z
next_multiple_of_3 = ugly[i3]*3
if ugly[1] == next_multiple_of_5:
i5 += z
next_multiple_of_5 = ugly[i5]*5
return ugly[-z]
def main():
n = 150
print (getNthUglyNo(n))
if __name__ == "__main__":
main()