Find the Nth ugly number in Java

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.

How to solve this problem

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.

• Enter a number N to find the Nth ugly number.
• A Boolean function isUgly(int n) takes a number 'n' as input and returns True if it is an ugly number, otherwise it returns False.
• An integer function findNthUgly(int n) takes 'n' as input and returns the nth ugly number as output.

Example

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);
   }
}

Output

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!