Lintcode4 Ugly Number II solution problem solution

[Title Description]

Ugly number is a number that only have factors 2, 3 and 5.

Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

Notice:Note that 1 is typically treated as an ugly number.

Design an algorithm to find the nth largest number containing only prime factors 2, 3, 5. The numbers that fit the criteria are: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

Note: we can think of 1 as an ugly number.

[Title Link]

http://www.lintcode.com/en/problem/ugly-number-ii/

[Title Analysis]

This is an extension of Merge Sort.

For any ugly number - K, 2*K, 3*K, and 5*K are ugly numbers, so new ugly numbers are generated by multiplying an existing ugly number by {2,3,5}.

if

Ugly Number: 1, 2, 3, 4, 5, 6, 8, 10, ..........

Then 1*2 2*2 3*2 4*2 5*2 6*2 8*2 10*2................................... 2

1*3 2*3 3*3 4*3 5*3 6*3 8*3 10*3 .......... *3

1*5 2*5 3*5 4*5 5*5 6*5 8*5 10*5 .......... *5

All are ugly numbers. Just keep adding the newly generated ugly number to the original ugly number array through merge sort until you find the Nth.

[Answer Link]

http://www.jiuzhang.com/solutions/ugly-number-ii/