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.
In Java, there are two ways or methods through which we can find the Nth 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
Output:
In the same way, we can also implement the code to check whether the given number is an Ugly number or not.
UglyNumberExample2.java
Output:
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[i2]*2;
mulitple3 = ugly[i3]*3
mulitple5 = ugly[i5]*5; - We use the looping statement for filling all the ugly numbers to the given range:
- At last, we return nextUglyNumber.
Let’s use the above steps and implement the actual code of it in Java.
UglyNumberExample3.java
Output: