Ugly Numbers

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 n and our task is to find the n^th ugly number and print its value.

Approach

Method 1: Naive Approach

​​Pseudocode

• 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 n^th ugly number.

Code

#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:

​​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+1^th 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 + 1^th) 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

• 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 n^th 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:

Code​

#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:

Complexity Analysis

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.