# Ugly Numbers

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

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]*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[1] = 2, two=1 , nm2 = ugly[two]x2 = ugly[1]x2 = 2×2 =4

ugly[n] = | 1 | 2 |

next = 2

second iteration

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

ugly[2] = 3, three=1 , nm3 = ugly[three]x3 = ugly[1]x3 = 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[3] = 4, two=2 , nm2 = ugly[two]x2 = ugly[2]x2 = 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[0] = 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[0] = 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 »
The text passage describes the concept of "ugly numbers" and provides both iterative and dynamic programming methods to find the nth ugly number. It includes code examples in C++ and Java, along with explanations and outputs for specific inputs.
multiple_questions_with_answers

the passage contains multiple implicit questions (e.g., "what is the 25th ugly number?" and "what is the 36th ugly number?"), and answers to these questions are provided in the form of outputs (54 and 120, respectively). additionally, the code examples themselves implicitly ask for the 9th ugly number, and the outputs (10) are provided.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Ugly Numbers

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

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]*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[1] = 2, two=1 , nm2 = ugly[two]x2 = ugly[1]x2 = 2×2 =4

ugly[n] = | 1 | 2 |

next = 2

second iteration

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

ugly[2] = 3, three=1 , nm3 = ugly[three]x3 = ugly[1]x3 = 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[3] = 4, two=2 , nm2 = ugly[two]x2 = ugly[2]x2 = 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[0] = 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[0] = 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 »
user
The text passage describes the concept of "ugly numbers" and provides both iterative and dynamic programming methods to find the nth ugly number. It includes code examples in C++ and Java, along with explanations and outputs for specific inputs.

TYPE: MULTIPLE_QUESTIONS_WITH_ANSWERS

The passage contains multiple implicit questions (e.g., "What is the 25th ugly number?" and "What is the 36th ugly number?"), and answers to these questions are provided in the form of outputs (54 and 120, respectively). Additionally, the code examples themselves implicitly ask for the 9th ugly number, and the outputs (10) are provided.