BlogsDope image BlogsDope

Ugly Numbers

Feb. 21, 2021 C JAVA C++ PYTHON ALGORITHM DATA STRUCTURE 528

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[0] := 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[0] = [1]
u2 = u3 = u5 = 0

i = 1
dpUgly[1] = 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[2] = 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[3] = 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[4] = 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[5] = 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[0] = 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[0] = 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 = [0] * n  
 
    dpUgly[0] = 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[1] 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.
Editor's Picks
0 COMMENT

Please login to view or add comment(s).