Given a number N, we have to write a code to find the Nth ugly number.
What is Ugly Numbers?
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. In simple words, The number which can be represented as the product of 2, 3 and 5 are ugly numbers (2^i * 3^i * 5^i).
For Example –
Input : n = 10, Output : 12
12 is the 10th ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12.
Note:
1 is typically treated as an ugly number.
n does not exceed 1690.
Nth Ugly Number
In this tutorial, I am going to discuss multiple approaches to solve this problem.
Programming questions on Binary Search
Programming questions on binary trees
Ugly Numbers – Java Code
The simplest approach to solve this problem is to run a loop from 1 until the nth ugly number is found.
How do we check whether a number is ugly or not?
Take a number, divide the number by greatest divisible powers of 2, 3 and 5, if the number becomes 1 then it is an ugly number otherwise not.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
//Ugly Number II - Java Code public class UglyNumbers { public int nthUglyNumber(int n) { int num = 0; while(n > 0) { num++; //If it's ugly, decrement n if(isUglyNumber(num)) n--; } return num; } private boolean isUglyNumber(int num) { num = divideNumber(num, 2); num = divideNumber(num, 3); num = divideNumber(num, 5); return num == 1; } private int divideNumber(int num, int factor) { while(num > 1 && num % factor == 0) { num = num/factor; } return num; } } |
Find Nth Ugly Number using Dynamic Programming – Java Code
We know the first ugly number is 1, We can generate the next ugly numbers by multiplying 2,3,5 with the previous ugly number.
So after 1 the next ugly number will be the Min of the multiple of 2, 3, 5 with 1. It is 2. Similarly, we can calculate next ugly number and so on.
The time complexity of this approach is O(n) and it’s space complexity is also O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
//Find Nth Ugly Number - Java Code public int nthUglyNumberUsingDp(int n) { if (n <= 0) return 0; List<Integer> uglyNumbers = new ArrayList<>(); //1 is considered as ugly number, Let's Add 1. uglyNumbers.add(1); int no2Indx = 0; int no3Indx = 0; int no5Indx = 0; while (uglyNumbers.size() < n) { int multiplyBy2 = uglyNumbers.get(no2Indx) * 2; int multiplyBy3 = uglyNumbers.get(no3Indx) * 3; int multiplyBy5 = uglyNumbers.get(no5Indx) * 5; int min = Math.min(multiplyBy2, Math.min(multiplyBy3, multiplyBy5)); uglyNumbers.add(min); if (min == multiplyBy2) no2Indx++; if (min == multiplyBy3) no3Indx++; if (min == multiplyBy5) no5Indx++; } return uglyNumbers.get(uglyNumbers.size()-1); } |
