# Ugly Numbers

Difficulty Level Easy
Frequently asked in Delhivery Goldman Sachs Paytm
MathViews 215

The positive numbers whose only prime factors are 2, 3, or 5 are known as ugly numbers. For eg- 8 is an ugly number because it’s an only prime factor is 2 but 7 is not an ugly number because it’s a prime factor is 7. 1 being an exception is included.

Input: 25

Output: 54

Input: 36

Output: 120

## Iterative Method for Ugly Numbers

### Algorithm for Ugly Numbers

1.  Initialize a variable count=1 to count the ugly numbers.
2.  Iterate over a variable i=1.
3.  Increment i by 1.
4.  Divide it by the greatest divisible powers of 2,3 and 5 and return the result.
5.  If the value of the result is 1 that is i is completely divisible by 2,3 or 5, increment the count.
6.  Repeat steps 3,4 and 5 until count=n.
7.  Return i.

Time Complexity: O(nlogn)

Space Complexity: O(1)

## C++ Program to find nthUgly Number

```#include <bits/stdc++.h>
using namespace std;

/* Function to divide the integer by
greatest divisible powers of 2,3,5 */
int Div(int x, int y){
while(x%y==0){
x=x/y;
}
return x;
}
/* Function to get the ugly
number*/
int uglyNo(int n){
int i=1;
int count=1;

while(n>count){
i++;
int p=i;
p=Div(p,2);
p=Div(p,3);
p=Div(p,5);
if(p==1){
count++;
}
}
return i;
}
int main(){
int n=9;
cout<<uglyNo(n);
return 0;
}
```
`Output : 10`

## Java Program to find nthUgly Number

```class Ugly{
/* Function to divide the integer by
greatest divisible powers of 2,3,5 */
static int Div(int x,int y){
while(x%y==0)
x=x/y;
return x;
}
/* Function to get the ugly
number*/
static int uglyNo(int n){
int i=1;
int count=1;
while(n>count){
i++;
int p=i;
p=Div(p,2);
p=Div(p,3);
p=Div(p,5);
if(p==1){
count++;
}
}
return i;
}
public static void main(String args[]){
int n=9;
int num = uglyNo(n);
System.out.println(num);
}
}
```
`Output : 10`

## Dynamic Programming Method for Ugly Numbers

In this method, only those numbers that are multiples of 2,3 and 5 are considered.

For eg- 2×1, 2×2, 2×3…….

3×1, 3×2, 3×3…….

5×1, 5×2, 5×3…….

The minimum ugly number is selected from these sequences at each step and the pointer increments by 1.

### Algorithm

1.  Initialize three-pointers two, three, and five pointing to zero.
2.  Take 3 variables nm2, nm3, and nm5 to keep track of next multiple of 2,3 and 5.
3.  Make an array of size n to store the ugly numbers with 1 at 0th index.
4.  Initialize a variable next which stores the value of the last element in the array.
5.  Run a loop n-1 times and perform steps 6,7 and 8.
6.  Update the values of nm2, nm3, nm5 as ugly[two]*2, ugly[three]*3, ugly*5 respectively.
7.  Select the minimum value from nm2, nm3, and nm5 and increment the pointer related to it.
8.  Store the minimum value in variable next and array.
9.  Return next.

### Explanation

Let n = 4

two=0, three=0, five=0, next=1

ugly[n] = | 1 |, nm2=2, nm3=3, nm5=5

first iteration

next = min(nm2, min(nm3, nm5))  = min(2, min(3, 5)) =2

ugly = 2, two=1 , nm2 = ugly[two]x2 = uglyx2 = 2×2 =4

ugly[n] = | 1 | 2 |

next = 2

second iteration

next = min(nm2, min(nm3, nm5))  = min(4, min(3, 5)) =3

ugly = 3, three=1 , nm3 = ugly[three]x3 = uglyx3 = 3×3 =9

ugly[n] = | 1 | 2 | 3 |

next = 3

third iteration

next = min(nm2, min(nm3, nm5))  = min(4, min(9, 5)) =4

ugly = 4, two=2 , nm2 = ugly[two]x2 = uglyx2 = 3×2 =6

After n-1 that is 3 iterations-

ugly[n] = | 1 | 2 | 3 | 4 |

next = 4     // The fourth ugly number is four

Time Complexity: O(n)

Space Complexity: O(n)

## C++ Program to find nthUgly Number

```#include<bits/stdc++.h>
using namespace std;

/* Function to get the nth ugly number*/
int uglyNo(int n){
int ugly[n], two=0, three=0, five=0;
int nm2=2, nm3=3, nm5=5, next=1;

ugly = 1;
for (int i=1; i<n; i++){
next = min(nm2,min(nm3,nm5));
ugly[i] = next;
if(next==nm2){
two++;
nm2 = ugly[two]*2;
}
if(next==nm3){
three++;
nm3 = ugly[three]*3;
}
if(next==nm5){
five++;
nm5 = ugly[five]*5;
}
}
return next;
}
int main(){
int n=9;
cout<<uglyNo(n);
return 0;
}```
`Output : 10`

## Java Program to find nthUgly Number

```import java.lang.Math;

class Ugly{
/* Function to get the nth ugly number*/
int uglyNo(int n){
int ugly[] = new int[n];
int two=0, three=0, five=0;
int nm2=2, nm3=3, nm5=5, next=1;

ugly = 1;

for(int i=1; i<n; i++){
next = Math.min(nm2, Math.min(nm3, nm5));

ugly[i] = next;
if(next == nm2){
two = two+1;
nm2 = ugly[two]*2;
}
if(next == nm3){
three = three+1;
nm3 = ugly[three]*3;
}
if(next == nm5){
five = five+1;
nm5 = ugly[five]*5;
}
}
return next;
}
public static void main(String args[]){
int n = 9;
Ugly obj = new Ugly();
System.out.println(obj.uglyNo(n));
}
}
```
`Output : 10`
Translate »