Ugly number in Java
Ugly number in Java
In Java, "Ugly numbers" refer to positive numbers whose prime factors are only 2, 3, and 5. 1 is also included grouped here for the sake of convention. The term is used in mathematics to describe numbers that are not visually pleasing but have important applications in computer science, particularly in the field of optimizing algorithms.
Let us consider some examples of Ugly numbers.
- 40
Prime factors of 40 are: 2 and 5
Thus, 40 falls into the category of an ugly number. - 56
Factors of 56 are: 2 and 7
Thus, 56 does not fall into the category of an ugly number. - 72
Factors of 72 are: 2 and 3
Thus, 72 falls into the category of an ugly number. - 10
Factors of 10 are: 2 and 5
Thus, 10 falls into the category of an ugly number. - 5
Factors of 5 are: 1 and 5
Thus, 5 falls into the category of an ugly number.
There are two approaches in which we can locate the Nth ugly number in Java. The following are these approaches:
- By using a for loop; the easiest approach
- Dynamic Programming
Let's examine each of the two approaches separately and then compare their reasoning.
1. By using a for loop
The loop is used in this approach for every positive number up until the ugly number count does not exceed n. When a number is ugly, we increase the counter variable. To determine if a number is ugly or not, we divide it by the highest 2, 3, and 5 divisors. A number is an ugly number when it becomes 1. That is not an ugly number if nothing else.
Let's understand both methods one by one and implement the logic of each of the above.
Implementation 1:
Algorithm:
Let us understand how the following program functions.
Step 1. Import the required classes and packages.
Step 2. Create a Java class named UglyNumber1 to hold the methods to check if a given number is an "Ugly number" or not.
Step 3. Define a static method named divideByGD(int n, int gdp) to divide the input number n by the greatest divisible power gdp until n is no longer divisible by gdp. This method returns the resulting value of n.
Step 4. Define a static method named checkUglyNumber(int n) to check if the given input number n is an "Ugly number" or not. The method first calls the divideByGD() method three times to divide n by 2, 3, and 5. If the resulting value of n is 1, the method returns true to indicate that the input number is an "Ugly number". Otherwise, the method returns false.
Step 5. Define the main() method of the UglyNumber1 class to take input from the user using the Scanner class, call the checkUglyNumber() method on the input number, and print a message to the console indicating whether the input number is an "Ugly number" or not.
Step 6. Compile the Java program and run it to check if a given input number is an "Ugly number" or not.
Overall, the program uses the divideByGD() and checkUglyNumber() methods to implement the algorithm for checking whether a given input number is an "Ugly number" or not. The program takes user input and returns a message indicating whether the input number is an "Ugly number" or not.
File name: UglyNumber1.java
//import the required classes and packages
import java.io.*;
import java.util.*;
//creation of a class named UglyNumber1 to check whether the given number is
// Ugly or not
class UglyNumber1 {
// creating a method named divideByGD() method to divide the no. by the given greatest divisible power
static int divideByGD(int n, int gdp)
{
while (n % gdp == 0)
n = n / gdp;
return n;
}
// creation of method named checkUglyNumber() that returns true when the number is an Ugly
static boolean checkUglyNumber(int n)
{
n = divideByGD(n, 2);
n = divideByGD(n, 3);
n = divideByGD(n, 5);
return (n == 1) ? true: false;
}
//main() method
public static void main(String args[])
{
int n1;
//get input from the user
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number you want to check - ");
n1 = sc.nextInt();
if (checkUglyNumber(n1))
System.out.println(n1 + " is an Ugly number.");
else
System.out.println(n1 + " is not an Ugly number.");
}
}
Output 1:
Output 2:
Complexity analysis:
Time Complexity: The overall time complexity of the given code is O (log n), where n is the value of the input number. This is because the divideByGD() method executes at most log(n) times, and this method is called three times in the checkUglyNumber() method.
Space Complexity: The space complexity of the code is O (1), as the amount of memory used by the program does not depend on the size of the input.
Top of Form
Implementation 2:
Algorithm:
Step 1: The program prompts the user to enter two integer values, n1 and n2, which represent the indices of the desired Ugly numbers.
Step 2: The program then creates a Scanner object to read the user input.
Step 3: The program calls the findNthUglyNumber() method twice, passing n1 and n2 as arguments.
Step 4: The findNthUglyNumber(int num) method initializes n to 1, and c to 1.
Step 5: The method then uses a while loop to increment n until it finds the num-th Ugly number, incrementing c each time it finds an Ugly number using the checkUglyNumber() method.
Step 6: The checkUglyNumber(int n) method uses the divideByGD() method to divide the number by 2, 3, and 5 until it is not divisible by any of them, and returns true if the resulting number is 1, otherwise false.
Step 7: The divideByGD(int n, int gdp) method divides the number n by the given greatest divisible power gdp until n is not divisible by gdp, and returns the resulting number.
Step 8: The findNthUglyNumber() method returns the num-th Ugly number.
Step 9: The program prints the n1-th and n2-th Ugly numbers using the System.out.println() method.
File name: UglyNumber2.java
//import the required classes and packages
import java.io.*;
import java.util.*;
//creation of class named UglyNumber1 to get Nth Ugly number
class UglyNumber2 {
// creation of a method divideByGD() method for dividing the number by the given greatest divisible power
static int divideByGD(int n, int gdp)
{
while (n % gdp == 0)
n = n / gdp;
return n;
}
// creation of checkUglyNumber() method that returns true when the number is an Ugly
static boolean checkUglyNumber(int n)
{
n = divideByGD(n, 2);
n = divideByGD(n, 3);
n = divideByGD(n, 5);
return (n == 1) ? true : false;
}
//create findNthUglyNumber() method for getting the nth Ugly number
static int findNthUglyNumber(int num)
{
int n = 1;
// initialize counter
int c = 1;
// using while loop to get Nth Ugly number
while (num > c) {
n++;
if (checkUglyNumber(n))
c++; //increment counter value
}
return n;
}
//main() method start
public static void main(String args[])
{
int n1, n2;
//creation of scanner class object to get input from user
Scanner sc = new Scanner(System.in);
//show the following message on the screen
System.out.println("Enter first nth value");
//store the value entered by user into variable n1
n1 = sc.nextInt();
// show the following message on the screen
System.out.println("Enter second nth value");
//store user entered value into variable n2
n2 = sc.nextInt();
System.out.println("The " + n1 + "th Ugly number is: " + findNthUglyNumber(n1));
System.out.println("The " + n2 + "th Ugly number is: " + findNthUglyNumber(n2));
}
}
Output:
Complexity Analysis:
The time complexity of the program is dominated by the findNthUglyNumber(int num) method, which has a time complexity of O(num).
The space complexity of the program is O (1) because it uses only a few integer variables and does not create any data structures.
2. Using Dynamic Programming
Another method that uses O(n) additional space is available to obtain the Nth ugly number. The first few ugly numbers in a row are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, and 15.
The aforementioned sequence can be divided into tree subsequences so that each group in the unsightly sequence looks like
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, …
We utilize the merging procedure as merge sort to extract each ugly number from the sequences.
We utilize dynamic programming to do the following procedures in order to obtain the Nth ugly number:
Initially, a number-ugly array is declared.
Implementation:
Algorithm:
Step 1. Import the required Java classes and packages and create a class here named UglyNumber3.
Step 2. Define a static method named findNthUglyNumber that takes an integer n as input and returns the nth ugly number.
Step 3. Declare an integer array here called uglyNumbers of size n to store the ugly numbers.
Step 4. Initialize three integer variables i2, i3, and i5 to 0, which will be used as array index variables for pointing to the first element of the ugly array.
Step 5. Initialize three integer variables m2, m3, and m5 to 2, 3, and 5 respectively.
Step 6. Initialize an integer variable nextUglyNumber to 1, which will be used to store the next ugly number.
Step 7. Set the first element of the uglyNumbers array to 1, since 1 is the first ugly number.
Step 8. Use a for loop to iterate from i = 1 to i < n.
Step 9. Within the for loop, calculate the next ugly number as the minimum of multiple2, multiple3, and multiple5.
Step 10. Store the next ugly number in the ith index of the uglyNumbers array.
Step 11. Use if statements to check if the nextUglyNumber equals multiple2, multiple3, or multiple5, and update the respective index variables i2, i3, and i5 and their corresponding multiples based on the nextUglyNumber value.
Step 12. End the for loop.
Step 13. Return the value of the nextUglyNumber as the nth ugly number.
Step 14. Define the main method.
Step 15. Create a Scanner object to read the input value of n.
Step 16. Prompt the user to enter the value of n.
Step 17. Read the input value of n from the user.
Step 18. Call the findNthUglyNumber method with n as input to find the nth ugly number.
Step 19. Print the result to the console.
File name: UglyNumber3.java
//import required classes and packages
import java.io.*;
import java.util.*;
//creation of class named UglyNumber3 to get the Nth ugly number
class UglyNumber3 {
//create findNthUglyNumber() method for getting the nth Ugly number
static int findNthUglyNumber(int n)
{
// declaration of an array of ugly numbers
int uglyNumbers[] = new int[n];
// Initializing 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 m2 = 2;
int m3 = 3;
int m5 = 5;
int nextUglyNumber = 1;
uglyNumbers[0] = 1;
for (int i = 1; i < n; i++)
{
nextUglyNumber = Math.min(m2, Math.min(m3, m5));
uglyNumbers[i] = nextUglyNumber;
if (nextUglyNumber == m2)
{
i2 = i2 + 1;
m2 = uglyNumbers[i2] * 2;
}
if (nextUglyNumber == m3)
{
i3 = i3 + 1;
m3 = uglyNumbers[i3] * 3;
}
if (nextUglyNumber == m5)
{
i5 = i5 + 1;
m5 = uglyNumbers[i5] * 5;
}
}
// End of for loop (i=1; i<n; i++)
return nextUglyNumber;
}
//main() method start
public static void main(String args[])
{
int nthNumber;
// use Scanner class to take input value of nthNumber
Scanner sc = new Scanner (System.in);
//display this message on the screen
System.out.println("Enter first nth value");
//store the entered value into variable nthNumber
nthNumber = sc.nextInt();
System.out.println("The " + nthNumber + "th Ugly number is: " + findNthUglyNumber(nthNumber));
}
}
Output 1:
Output 2:
Complexity Analysis:
This Java code finds the nth ugly number, which is a positive number whose prime factors are only 2, 3, or 5. The time complexity of this algorithm is O(n), as it iterates through loop n times to find the nth ugly number.
The space complexity of this algorithm is also O(n), as an array of size n is used to store the ugly numbers.