UVa 136

From Algorithmist
Jump to navigation Jump to search

136 - Ugly Numbers[edit]

Summary[edit]

Since there is no input to this problem (you only need to print a certain string), brute forcing will be fine done locally. The number will fit comfortably into a 32-bit signed integer. Instead of brute forcing it, you could use dynamic programming to build up the solution or you could simply build the sequence bottom-up.

Explanation[edit]

This problem uses the fact that is an ugly number if is an ugly number (with ). We can then use Dynamic Programming to fill in the rest.
To build the sequence of ugly numbers in increasing sequence, we need an array to keep the first 1500 ugly numbers and three pointers which will indicate the smallest ugly number which was not multiplied by 2, 3 or 5 yet and which, if multiplied with one of 2, 3 or 5 will yield a number greater than the number at the end of our built sequence. At the beginning of the algorithm, the first element of the sequence will be 1 and all the pointers will indicate to it. See second code below for clarrifications.

Input[edit]

There is no input to this problem.

Output[edit]

There is only one output to this problem.

References[edit]

Ugly numbers are 5-smooth numbers:

Solution[edit]


See also UVa_443