WAP to Find nth Ugly Number.

Assume N can be number from 1 to 1000

A number is said to be ugly if it has prime factors of 2,3,5 only.

Eg: 2 3 4 5 6 8 9 10 12 15 ....

Input : n = 7

Output : 9

Input : n = 10

Output : 15

Input : n = 15

Output : 25

Input : n = 150

Output : 6000

Process:

Keep dividing the number by 2 till it is possible.

Keep dividing the number by 3 till it is possible.

Keep dividing the number by 5 till it is possible.

If it is left with 1 as reminder it is Ugly Number.

Eg: 300

If divided constantly by 2, will become 150 and then 75.

Now 75 divided constantly by 3, will become 25

Now 25 divided constantly by 5, will become 5 and then 1.

Finally reminder is 1, hence 300 is an ugly Number.

```
public class UglyNumberWithOutDP {
public static void main(String[] args) {
int uglyNumberCount=0;
int n=10;
for(int i=2;i<Integer.MAX_VALUE;i++){
int num=i;
while(num%2==0){num=num/2;}
while(num%3==0){num=num/3;}
while(num%5==0){num=num/5;}
if(num==1){
uglyNumberCount++;
}
if(uglyNumberCount==n) {
System.out.println("Ugly Number :"+i);
break;
}
}
}
}
```

Published By : Suraj Ghimire