Monday, August 31, 2009

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
........
........

No comments:

Post a Comment