# UVa 136

Jump to navigation Jump to search

## Summary

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

This problem uses the fact that ${\displaystyle n}$ is an ugly number if ${\displaystyle n/i,i\in (2,3,5)}$ is an ugly number (with ${\displaystyle i\mid n}$). 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

There is no input to this problem.

## Output

There is only one output to this problem.

## References

Ugly numbers are 5-smooth numbers:

See also UVa_443