Algorithm of 136 - Ugly Numbers

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

No comments:

Post a Comment

Write your comment - Share Knowledge and Experience