**ID :** UVA – 136 – Ugly Numbers
**Submissions :** Java –** Accepted**
**Difficulty :** Easy
**Type : **Number Theory , Factorization , Dynamic Programming
**Time for Submission :** 2 Hours
**Solution Description :**
- this problem can be solved dynamically using the fact that any ugly number is composed of a previous ugly number, multiplied by 2, 3 or 5.
- so you loop each time through all the previous ugly numbers multiply each of them by 2, 3 & 5 and check which one is the least next one.
- but for more optimization, you can keep track only of the most recent 3 numbers in-queue that when multiplied by one of the mentioned factors will produce a number that will come after the latest ugly number. and each time you find their minimum and advance its pointer

**Problems :**
- No Problems, it went smoothly 🙂

**Code :**

public class Main {
public static void main(String[] args) {
int ugly[] = new int[1501], ps[] = {1,1,1}, factors[] ={ 2,3,5 };
ugly[1] =1;
for(int i=2; i<=1500;i++){
ugly[i] = Math.min(2*ugly[ps[0]], Math.min(3*ugly[ps[1]], 5*ugly[ps[2]]));
for(int j=0; j<ps.length; j++)
if(factors[j]*ugly[ps[j]]==ugly[i]) ps[j]++;
}
System.out.format("The 1500'th ugly number is %d.\n",ugly[1500]);
}
}

### Like this:

Like Loading...

*Related*