Ugly number Java

The Ugly number is another special positive number in Java. If a number has only 2, 3, or 5 prime factors and by convention 1 is also included, the number is called Ugly number.

Let’s take some examples of Ugly numbers.

27 is not an Ugly number because its prime factors contain 7.
12 is an Ugly number because its prime factors are 2 and 3.
28 is also not an Ugly number because its prime factors also contain 7.
16 is an Ugly number because its prime factors only contain 2.

Ugly number Java

In Java, there are two ways or methods through which we can find the N^th Ugly number. These methods are as follows:

The simple method using for loop
Use Dynamic Programming

Let’s understand both the methods one by one implement the logic of each one.

The simple method using for loop

In this method, we use the loop for each positive number until the Ugly number count is not greater than n. We increment the counter variable when the number is Ugly, and to check whether the number is Ugly or not, we divide the number by the greatest divisible powers of 2, 3, and 5. When the number becomes 1, it is an Ugly number. Otherwise, it is not an Ugly number.

Let’s implement the code to get Nth Ugly number in Java.

UglyNumberExample1.java

  //import required classes and packages  import java.io.*;  import java.util.*;    //create UglyNumberExample1 class to get Nth Ugly number  class UglyNumberExample1 {         // create a method divideByGreatestDivisible() method for dividing the number by the given greatest divisible power      static int divideByGreatestDivisible(int number, int gdp)      {          while (number % gdp == 0)              number = number / gdp;          return number;      }         // create checkUglyNumber() method that returns true when the number is an Ugly      static boolean checkUglyNumber(int number)      {          number = divideByGreatestDivisible(number, 2);          number = divideByGreatestDivisible(number, 3);          number = divideByGreatestDivisible(number, 5);             return (number == 1) ? true : false;      }         //create findNthUglyNumber() method for getting the nth Ugly number      static int findNthUglyNumber(int NthNumber)      {          int number = 1;             // initialize counter          int counter = 1;             // using  while loop to get Nth Ugly number          while (NthNumber > counter) {              number++;              if (checkUglyNumber(number))                  counter++;//increment counter value          }          return number;      }         //main() method start      public static void main(String args[])      {            int NthNumber1, NthNumber2;    //create scanner class object to get input from user  Scanner sc = new Scanner(System.in);    //show custom message  System.out.println(“Enter first Nth value”);    //store user entered value into variable NthNumber1  NthNumber1 = sc.nextInt();    //show custom message  System.out.println(“Enter second Nth value”);    //store user entered value into variable NthNumber2  NthNumber2 = sc.nextInt();            System.out.println(“The ” + NthNumber1 + “th Ugly number is: ” + findNthUglyNumber(NthNumber1));  System.out.println(“The ” + NthNumber2 + “th Ugly number is: ” + findNthUglyNumber(NthNumber2));      }  }  

Output:

Ugly number Java

In the same way, we can also implement the code to check whether the given number is an Ugly number or not.

UglyNumberExample2.java

  //import required classes and packages  import java.io.*;  import java.util.*;    //create UglyNumberExample2 class to check whether the given numbers are Ugly or not  class UglyNumberExample2 {         // create a method divideByGreatestDivisible() method for dividing the number by the given greatest divisible power      static int divideByGreatestDivisible(int number, int gdp)      {          while (number % gdp == 0)              number = number / gdp;          return number;      }         // create checkUglyNumber() method that returns true when the number is an Ugly      static boolean checkUglyNumber(int number)      {          number = divideByGreatestDivisible(number, 2);          number = divideByGreatestDivisible(number, 3);          number = divideByGreatestDivisible(number, 5);             return (number == 1) ? true : false;      }         //main() method start      public static void main(String args[])      {            int number1, number2;    //get input from user  Scanner sc = new Scanner(System.in);  System.out.println(“Enter first number to check”);  number1 = sc.nextInt();    System.out.println(“Enter second number to check”);  number2 = sc.nextInt();    if (checkUglyNumber(number1))               System.out.println(number1 + ” is an Ugly number.”);           else              System.out.println(number1 + ” is not an Ugly number.”);    if (checkUglyNumber(number2))               System.out.println(number2 + ” is an Ugly number.”);           else              System.out.println(number2 + ” is not an Ugly number.”);      }  }  

Output:

Ugly number Java

Using Dynamic Programming

There is another way of getting the Nth Ugly number that takes O(n) extra space. The series of starting few Ugly numbers is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ……..

We can split the above sequence into tree subsequences in such a way that each group in an ugly sequence like as

1×2, 2×2, 3×2, 4×2, 5×2, …
1×3, 2×3, 3×3, 4×3, 5×3, …
1×5, 2×5, 3×5, 4×5, 5×5, …

In order to get each ugly number from the sequences, we use the merge method as merge sort.

These are the following steps which we use to get the Nth ugly number using dynamic programming:

First, we declare an array for ugly numbers.
1 is the first ugly number, so we initialize it our program as first ugly number.
Next, we initialize i2, i3, i5 as array index variables for pointing to the 1st element of the ugly array:
i2 = i3 = i5 =0;
Initializing choices to next ugly number like as
mulitple2 = ugly[i₂]*2;
mulitple3 = ugly[i₃]*3
mulitple5 = ugly[i₅]*5;
We use the looping statement for filling all the ugly numbers to the given range:

  for (i = 1; i <range; i++ )   {  nextUglyNumber  = Min(mulitple2, mulitple3, mulitple5);   ugly[i] =  nextUglyNumber  if (nextUglyNumber  == mulitple2)   {               i2 = i2 + 1;          mulitple2 = ugly[i2]*2;  }   if (nextUglyNumber  == mulitple3)   {               i3 = i3 + 1;          mulitple3 = ugly[i3]*3;  }              if (nextUglyNumber  == mulitple5)  {      i5 = i5 + 1;          mulitple5 = ugly[i5]*5;  }   }   

At last, we return nextUglyNumber.

Let’s use the above steps and implement the actual code of it in Java.

UglyNumberExample3.java

  //import required classes and packages  import java.io.*;  import java.util.*;    //create UglyNumberExample1 class to get the Nth ungly number  class UglyNumberExample3 {         //create findNthUglyNumber() method for getting the nth Ugly number      static int findNthUglyNumber(int number)      {           // declare an array for ugly numbers          int uglyNumbers[] = new int[number];    //we initialize i2, i3, i5  as array index variables for pointing to the 1st element of the ugly array:           int i2 = 0, i3 = 0, i5 = 0;            int multiple2 = 2;          int multiple3 = 3;          int multiple5 = 5;            int nextUglyNumber = 1;             uglyNumbers[0] = 1;             for (int i = 1; i < number; i++)          {              nextUglyNumber = Math.min(multiple2, Math.min(multiple3, multiple5));                 uglyNumbers[i] = nextUglyNumber;              if (nextUglyNumber == multiple2)              {                  i2 = i2 + 1;                  multiple2 = uglyNumbers[i2] * 2;              }              if (nextUglyNumber == multiple3)              {                  i3 = i3 + 1;                  multiple3 = uglyNumbers[i3] * 3;              }              if (nextUglyNumber == multiple5)              {                  i5 = i5 + 1;                  multiple5 = uglyNumbers[i5] * 5;              }          }                     // End of for loop (i=1; i<n; i++)          return nextUglyNumber;      }         //main() method start      public static void main(String args[])      {            int NthNumber1, NthNumber2;    // use Scanner class for taking value of NthNumber1 and NthNumber2  Scanner sc = new Scanner(System.in);    //show custom message  System.out.println(“Enter first Nth value”);    //store user entered value into variable NthNumber1  NthNumber1 = sc.nextInt();    //show custom message  System.out.println(“Enter second Nth value”);    //store user entered value into variable NthNumber2  NthNumber2 = sc.nextInt();            System.out.println(“The ” + NthNumber1 + “th Ugly number is: ” + findNthUglyNumber(NthNumber1));  System.out.println(“The ” + NthNumber2 + “th Ugly number is: ” + findNthUglyNumber(NthNumber2));      }  }  

Output:

Ugly number Java

Next TopicAchilles Number in Java

Ugly number Java

Ugly number Java

The simple method using for loop

Using Dynamic Programming

Special Number in Java

JavaScript Array entries() Method

You may also like