Problem Description Link
This problem can be solved following stapes:
1. Generate a list of ugly numbers bottom to up
example:
if we know that '1' is the first ugly number and the only prime factors are 2,3,5, then
the next ugly number will be min(2*1,3*1,5*1) which is 2.
when we know that '1' and '2' are the first 2 ugly numbers,
the next ugly number will be min(2*2,3*1,5*1) which is 3.
N.B: factor 2 is now multiplied with '2' whereas the rest are still multiplied with '1'.
2. Brute force, enumerate the numbers one by one incrementally, and check whether their prime factors are only 2,3,5...
3. so you can get series of ugly number 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
4. just print the 1500th ugly number.
This problem can be solved following stapes:
1. Generate a list of ugly numbers bottom to up
example:
if we know that '1' is the first ugly number and the only prime factors are 2,3,5, then
the next ugly number will be min(2*1,3*1,5*1) which is 2.
when we know that '1' and '2' are the first 2 ugly numbers,
the next ugly number will be min(2*2,3*1,5*1) which is 3.
N.B: factor 2 is now multiplied with '2' whereas the rest are still multiplied with '1'.
2. Brute force, enumerate the numbers one by one incrementally, and check whether their prime factors are only 2,3,5...
3. so you can get series of ugly number 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
4. just print the 1500th ugly number.
No comments:
Post a Comment
Write your comment - Share Knowledge and Experience