# Ugly Numbers

Feb. 21, 2021 528
Download Our App. Dynamic Programming is a popular DSA concept and today we shall be discussing one such problem that tests your understanding of the dynamic programming concepts.

## ​Problem Description

This problem is based on "Ugly Numbers". Ugly numbers are numbers whose only prime factors are 2, 3 or 5. For example, the first 11 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, and 15 where 1 is included by convention. 7, 11 and 13 are not ugly numbers as their prime factors are other than 2, 3 and 5. In this problem, we shall be provided with a value and our task is to find the nth ugly number and print its value.

​Example:

Input: n = 6

Output: 6
Input: n = 8
Output: 9
Input: n = 100

Output: 1536

## Approach

This problem can be solved using two approaches. The first one is the naive approach which uses no extra space but has greater time complexity and the other is the dynamic programming approach that decreases the time complexity by increasing the space complexity. Let's have a look at both of these approaches:

### Method 1: Naive Approach

This is the simple brute-force method to find whether the a number is ugly or not. We traverse numbers using a loop until our ugly number count is not equal to n and successively keep on increasing the ugly number count if a number is ugly. To check if a number is ugly or not, we simply divide the number by greatest divisible powers of 2, 3 and 5, repeatedly and if the number becomes 1 then it is an ugly number otherwise not. The illustration below shows how to check for an ugly number using brute-force approach.

### ​​Pseudocode

succesiveDivision(x, y)
while x%y = 0, do

x := x/y

return x

uglyCheck(num)

num := succesiveDivision(num, 2)

num := succesiveDivision(num, 3)

num := succesiveDivision(num, 5)

if num = 1, then

return True

else

return False

nthUgly(n)

i = 1

count = 1

while n > count, do

i := i + 1

if uglyCheck(i) = True, then

count := count + 1

return i

• In the above pseudocode, the first function succesiveDivision() is the main part of our code. It continuously divides the number x by y until x is no longer divisible by y. In this way we can find the greatest powers of 2,3 and 5 and return the number after dividing it with these greatest power values.
• The second function, i.e. uglyCheck() simply checks whether a number is ugly by dividing it with the highest divisible powers of 2,3 and 5. If the number after all three divisions is equal to 1 then it returns True otherwise it returns False.
• The third method, nthUgly() simply checks through all the integer values starting from 1, until the ugly number count is equal to n and we have our nth ugly number.

Code

• C/C++
• Java
• Python
#include <iostream>
using namespace std;

// Function for successive divisions
int succesiveDivision(int x, int y)
{
while (x % y == 0)
x = x / y;
return x;
}

//  Function for checking if a number is ugly or not
bool uglyCheck(int num)
{
num = succesiveDivision(num, 2);
num = succesiveDivision(num, 3);
num = succesiveDivision(num, 5);

if (num == 1)
return true;
else
return false;
}

// Function for finding the nth ugly number
int nthUgly(int n)
{

int i = 1;

// ugly number count
int count = 1;

// Looping through all integers until ugly count becomes n
while (n > count) {
i++;
if (uglyCheck(i))
count++;
}
return i;
}

// Driver Code
int main()
{
// Function call
int no = nthUgly(100);
cout<< "100th ugly no. is: "<< no;

return 0;
}

class UglyNumber {

// Function for successive divisions
static int succesiveDivision(int x, int y)
{
while (x % y == 0)
x = x / y;
return x;
}

//Function for checking if a number is ugly or not
static boolean uglyCheck(int num)
{
num = succesiveDivision(num, 2);
num = succesiveDivision(num, 3);
num = succesiveDivision(num, 5);

if (num == 1)
return true;
else
return false;
}

// Function for finding the nth ugly number
static int nthUgly(int n)
{

int i = 1;

// ugly number count
int count = 1;

// Looping through all integers until ugly count becomes n
while (n > count) {
i++;
if (uglyCheck(i))
count++;
}
return i;
}

/* Driver Code*/
public static void main(String args[])
{
int no = nthUgly(100);

System.out.println("100th ugly no. is: " + no);
}
}

# Function for successive divisions
def succesiveDivision(x, y):
while x % y == 0:
x = x / y
return x

# Function for checking if a number is ugly or not
def uglyCheck(num):
num = succesiveDivision(num, 2)
num = succesiveDivision(num, 3)
num = succesiveDivision(num, 5)
if num == 1:
return True
else:
return False

# Function for finding the nth ugly number
def nthUgly(n):
i = 1
# ugly number count
count = 1

# Looping through all integers until ugly count becomes n
while n > count:
i += 1
if uglyCheck(i):
count += 1
return i

# Driver code
no = nthUgly(100)
print("100th Ugly number is:", no)


Output:

​100th Ugly number is: 1536

### ​​Method 2: Dynamic Programming

In this approach, we can make use the already calculated ugly numbers in order to skip our iterations and reduce the time complexity. Suppose that we have k ugly numbers already, then the k+1th ugly number has to be some multiple of the previous ugly numbers only otherwise it would not remain ugly because this way the prime factors of the new number (k + 1th) will only be 2, 3 and 5.

Thus, we divide the numbers into sequence of three series that are divisible by 2, 3, and 5 as shown in the picture given below. Every one of these subsequence is ugly subsequence in itself, so, at every step we choose the smallest one from the three sequences, and move one step after. By keeping a track of where last multiple of each (2,3,5) was kept in the dp array, we don't need to consider ugly numbers previous to those. With Dynamic Programming, we only consider the Ugly numbers and don't check the non Ugly ones.

Let's look at the code first and then its explanation.

### Pseudocode

nthUgly(n)
Declare := dpUgly[n]
dpUgly := 1
u2 = u3 = u5 := 0
multiple_2 := 2
multiple_3 := 3
multiple_5 := 5

for i in 1 to n, do
dpUgly[i] := minimum(multiple_2,multiple_3,multiple_5)

if dpUgly[i] = multiple_2, then
u2 = u2 + 1
multiple_2 := dpUgly[u2] * 2

if dpUgly[i] = multiple_3
u3 = u3 + 1
multiple_3 := dpUgly[u3] * 3

if dpUgly[i] = multiple_5
u5 = u5 + 1
multiple_5 := dpUgly[u5] * 5

return dpUgly[n-1]

• In the above function nthUgly(), we first declare a dynamic programming array to store the ugly numbers. We initialize the first ugly number as 1 and set the pointers for multiples for 2, 3 and 5. We also set counters for storing the multiples of 2, 3, and 5 respectively.
• After that we loop from 1 to n and at each step, we find the minimum ugly number out of the three multiples and store it in our dp array. We also increase the pointer for the number whose multiple has been added and replace it by its next multiple. So, suppose a multiple of 2 has been added to the array, we increase 2's pointer by 1 and multiply the previous multiple by 2 to get the next multiple and similar work goes on for other numbers as well.
• In this way starting from the base case, we generate all the ugly numbers and then apply dynamic programming to store the numbers into the array until we get the nth ugly number.

This approach is better than the previous naïve approach because instead of  checking all the numbers for being ugly, we just use the previous ugly numbers to generate new ones. Let us see the working of the pseudocode with an example:

dpUgly = 
u2 = u3 = u5 = 0

i = 1
dpUgly = Min(dpUgly[u2]*2, dpUgly[u3]*3, dpUgly[u5]*5) = Min(2, 3, 5) = 2
dpUgly[] = [1, 2]
u2 = 1, u3 = u5 = 0 (u2 incremented)

i = 2
dpUgly = Min(dpUgly[u2]*2, dpUgly[u3]*3, dpUgly[u5]*5) = Min(4, 3, 5) = 3
dpUgly[] = [1, 2, 3]
u2 = 1, u3 = 1, u5 = 0 (u3 incremented)

i = 3
dpUgly = Min(dpUgly[u2]*2, dpUgly[u3]*3, dpUgly[u5]*5) = Min(4, 6, 5) = 4
dpUgly[] = [1, 2, 3, 4]
u2 = 2, u3 = 1, u5 = 0 (u2 incremented)

i = 4
dpUgly = Min(dpUgly[u2]*2, dpUgly[u3]*3, dpUgly[u5]*5) = Min(6, 6, 5) = 5 dpUgly[] = [1, 2, 3, 4, 5]
u2 = 2, u3 = 1, u5 = 1 (u5 incremented)

i = 5
dpUgly = Min(dpUgly[u2]*2, dpUgly[u3]*3, dpUgly[u5]*5) = Min(6, 6, 10) = 5 dpUgly[] = [1, 2, 3, 4, 5, 6]
u2 = 3, u3 = 2, u5 = 1 (u2 & u3 incremented)

This process continues, till we get n elements in dpUgly[] array.

Code

• C/C++
• Java
• Python
#include <iostream>

using namespace std;

// Function to get the nth ugly number
int nthUgly(int n)
{
// dp array to store ugly numbers
int dpUgly[n];
dpUgly = 1;

// u2, u3, u5 are indices for multiples of 2,3,5 respectively
int u2 = 0, u3 = 0, u5 = 0;

// Set initial multiple value
int multiple_2 = 2;
int multiple_3 = 3;
int multiple_5 = 5;

for (int i = 1; i < n; i++) {
// Choosing minimum value of all available multiples
dpUgly[i] = min(multiple_2,min(multiple_3,multiple_5));

// Increment the value of index accordingly
if(dpUgly[i] == multiple_2)
{
u2++;
multiple_2 = dpUgly[u2] * 2;
}
if(dpUgly[i] == multiple_3)
{
u3++;
multiple_3 = dpUgly[u3] * 3;
}

if(dpUgly[i] == multiple_5)
{
u5++;
multiple_5 = dpUgly[u5] * 5;
}
}

// Returning dpUgly[n] value
return dpUgly[n-1];
}

// Driver Code
int main()
{
int n = 100;
cout<<"100th Ugly number is: " << nthUgly(n);
return 0;
}

import java.lang.Math;

public class UglyNumber
{
static int nthUgly(int n)
{
// dp array to store ugly numbers
int dpUgly[] = new int[n];
dpUgly = 1;

// u2, u3, u5 are indices for multiples of 2,3,5 respectively
int u2 = 0, u3 = 0, u5 = 0;

// Set initial multiple value
int multiple_2 = 2;
int multiple_3 = 3;
int multiple_5 = 5;

for (int i = 1; i < n; i++)
{
// Choosing minimum value of all available multiples
dpUgly[i] = Math.min(multiple_2,Math.min(multiple_3,multiple_5));

// Increment the value of index accordingly
if(dpUgly[i] == multiple_2)
{
u2++;
multiple_2 = dpUgly[u2] * 2;
}
if(dpUgly[i] == multiple_3)
{
u3++;
multiple_3 = dpUgly[u3] * 3;
}

if(dpUgly[i] == multiple_5)
{
u5++;
multiple_5 = dpUgly[u5] * 5;
}
}

// Returning dpUgly[n] value
return dpUgly[n-1];

}

// Driver code
public static void main(String args[])
{

int n = 100;

System.out.println("100th Ugly number is: "+nthUgly(n));
}
}

def nthUgly(n):

# dp array to store ugly numbers
dpUgly =  * n

dpUgly = 1

# u2, u3, u5 are indices for multiples of 2,3,5 respectively
u2 = u3 = u5 = 0

# Set initial multiple value
multiple_2 = 2
multiple_3 = 3
multiple_5 = 5

# Loop to find value from ugly to ugly[n]
for i in range(1, n):
# Choosing minimum value of all available multiples
dpUgly[i] = min(multiple_2,multiple_3,multiple_5)

# Increment the value of index accordingly
if dpUgly[i] == multiple_2:
u2 += 1
multiple_2 = dpUgly[u2] * 2

if dpUgly[i] == multiple_3:
u3 += 1
multiple_3 = dpUgly[u3] * 3

if dpUgly[i] == multiple_5:
u5 += 1
multiple_5 = dpUgly[u5] * 5

# Returning dpUgly[n] value
return dpUgly[n-1]

# Driver code
n = 100
print("100th ugly number is:",nthUgly(n))


Output:

100th ugly number is: 1536

### Complexity Analysis

Approach
TIme Complexity
Space Complexity
Naïve Approach
O(nlogn)
O(1)
Dynamic Programming Approach
O(n)
O(n)

The naïve approach checks for the ugliness of a number by sucessive divisions and this step takes logn time it is repeated until nth number is found thus resulting in O(nlogn) time complexity. SInce no extra space is used, the space complexity is O(1).

The dynamic programming approach maintains a dp array to store the Ugly numbers and this way we only have to traverse till the array of size n is filled. This makes the time complexity as O(n) and the extra array used makes the space complexity as O(n) as well.

In this way we have seen three approaches to solve the "Ugly Numbers" problem.

Liked the post?
Zealous Learner.
0 COMMENT

Please login to view or add comment(s).