A number that has only 2, 3 or 5 as prime factors is called an ugly number. Some ugly numbers include: 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, etc.
We have a number N, and the task is to find the Nth ugly number in the sequence of ugly numbers.
For example:
Input-1:
N = 5
Output:
5
Explanation:
The 5th ugly number in the sequence of ugly numbers [1, 2, 3, 4, 5, 6, 8, 10, 12, 15] is 5.
Input-2:
N = 7
Output:
8
Explanation:
In the ugly number sequence [1, 2, 3, 4, 5, 6, 8, 10, 12, 15], the seventh ugly number is 8.
A simple way to solve this problem is to check if the given number is divisible by 2, 3 or 5 and follow the sequence until the given number. Now find if the number satisfies the conditions for all ugly numbers and return that number as output.
Demo
public class UglyN { public static boolean isUglyNumber(int num) { boolean x = true; while (num != 1) { if (num % 5 == 0) { num /= 5; } else if (num % 3 == 0) { num /= 3; } // To check if number is divisible by 2 or not else if (num % 2 == 0) { num /= 2; } else { x = false; break; } } return x; } public static int nthUglyNumber(int n) { int i = 1; int count = 1; while (n > count) { i++; if (isUglyNumber(i)) { count++; } } return i; } public static void main(String[] args) { int number = 100; int no = nthUglyNumber(number); System.out.println("The Ugly no. at position " + number + " is " + no); } }
The Ugly no. at position 100 is 1536.
The above is the detailed content of Find the Nth ugly number in Java. For more information, please follow other related articles on the PHP Chinese website!