“Ugly numbers are numbers whose only prime factors are 2, 3
or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
Shows the first 11 ugly numbers. By convention, 1 is
included.
Write a program to find and print the 1500'th ugly number.”
Category: Dynamic Programming
Solution:
Build an array to store the ugly number until reaching the
1500^{th} number.
The next ugly number is the minimum of all the
previous ugly numbers multiplied by 2, 3 or 5.
Example:
Ugly Number

1


Index

0

1

2

3

4

5

To find the next ugly number at index 1:
1x2 = 2, 1x3 = 3, 1x5 = 5 and the minimum is 2.
Ugly Number

1

2


Index

0

1

2

3

4

5

To find the next ugly number at index 2:
1x2 = 2, 1x3 = 3, 1x5 = 5
2x2 = 4, 2x3 = 6, 2x5 = 10
The minimum is 3 (greater than 2) but note that we didn’t
really need to multiply (1x2=2) since it is less than or equal to the current
ugly number.
To limit the search to only the numbers that are relevant we
maintain 3 indices:
Index2: is the minimum index when multiplied by 2 will be
greater than our current ugly number. In the example index2=1. (avoid 1x2).
Apply the same definition to index3 and index5.
Solution Source (Coding Interviews: Questions, Analysis
& Solutions).
The 1500'th ugly number is 859963392.
Code:
No comments:
Post a Comment