info@onlinelearningcenter.in (+91) 7 999 01 02 03 Get started with 60 Hours of Free course right now 

Ugly Number

Suraj Ghimire
40 Posts

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
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Comments