Notes: 136 - Ugly Numbers

“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:

Notes