136 - Ugly Numbers - UVA

Ad Hoc OR Dynamic Programming

You can pre-calculate calculate the answer by checking all the numbers till you find the 1500'th ugly number by checking each number prim factors to see whether they are just 2, 3 and 5.

OR

You can build a list of ugly numbers in a bottom-up dynamic programming approach. How?

I use a set and a vector of integers for simplicity. Both the set and the vector have the same numbers, I can use just a set too without no vectors.

I must build the list of ugly numbers, since my first ugly number in the list is 1, so the next one must be retrieved by multiplying 2, 3 and 5 by 1 ( the first number in the list ). I pick 2*1 ( the minimum ), then 2 must be multiplied by the next number in the list( 2 ). At next step I choose 3 out of ( 2*2, 3*1, 5*1 ), and 3 must be multiplied by 2( the next number in the list for factor 3 ), then I pick 4 out of ( 2*2, 3*2, 5*1 ) and so on.

2*1     3*1     5*1

2*2    3*2    5*2

2*3    3*3    5*3

2*4    3*4 

2*5

2*6

My function min3 is invoked in this order:

2*1,   3*1,   5*1

2*2,   3*1,   5*1

2*2,   3*2,   5*1

2*3,   3*2,   5*1

2*3,   3*2,   5*2

2*4,   3*2,   5*2

2*4,   3*3,   5*2

2*5,   3*3,   5*2

2*5,   3*4,   5*2

2*6,   3*4,   5*2

2*6,   3*4,   5*3

2*8,   3*4,   5*3

2*8,   3*5,   5*3

........

........