Home » Algorithms

Finding Ugly Number using Dynamic Programming (DP)

Here, we are going to learn what ugly number is and how to find ugly number using dynamic programming (DP)?
Submitted by Ritik Aggarwal, on December 11, 2018

Problem: You are given N. You have to find N^th ugly number. 1^st ugly number is 1.

Constraints: 1 <= N <= 10000

Examples:

    Input:
    10
    
    Output:
    10th ugly number is 12
    
    
    Input:
    724
    
    Output:
    724th ugly number is 7085880

Explanation of the problem:

Ugly numbers are those number whose only prime factors are 2, 3, 5 (except 1). 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ..., So our 10^th ugly number is 12.

Solution:

The basic and the brute force approach for solving this problem is to iterate over all the numbers and check whether it is ugly or not then incrementing the counter but this approach will be highly inefficient to solve. Therefore, we will discuss the Dynamic Programming approach. Now we will take a dp matrix in which i^th cell represent ith ugly number. Then we will find the answer to ugly number using this dp relation.

Ugly number(i) = minimum of (2*ugly number(f2), 3*ugly number(f3), 5*ugly number(f5))

Where, f2, f3, f5 are counters for 2, 3, 5 respectively which stores the index for f2^th ugly number, f3^th ugly number, f5^th ugly number.

Then we will store our answer.

Algorithm:

1. Initializing f2, f3, f5 to maintain f2^th ugly number, f3^th ugly number and f5^th ugly number to 1.
2. Creating a DP matrix in which ith cell represent i^th ugly number.
3. Start filling the dp matrix from i = 2.
4. Ugly number(i) = minimum of (2*ugly number(f2), 3*ugly number(f3), 5*ugly number(f5)).
5. Finding the answer using above relation and storing it at i^th index.

Now, the time complexity of the above code is O(N).

Program:

#include <iostream>
using namespace std;

long long int uglyNumber(int n){
	// f2 maintains the index of the ugly number 
	// for multiplication by 2
	int f2 = 1;
	// f3 maintains the index of the ugly number 
	// for multiplication by 3
	int f3 = 1;
	// f5 maintains the index of the ugly number 
	// for multiplication by 5
	int f5 = 1;
	long long int dp[n + 1] = {0};
	// first ugly number is 1
	dp[1] = 1;
	// filling the dp matrix from i = 2
	for(int i = 2;i<=n;i++){
		// calculating the next number from previous ugly numbers
		long long int ans_f_2 = dp[f2] * 2;
		long long int ans_f_3 = dp[f3] * 3;
		long long int ans_f_5 = dp[f5] * 5;
		// finding minimum of all the answer
		long long int final_ans = min(ans_f_2, min(ans_f_3, ans_f_5));
		// storing the ans
		dp[i] = final_ans;
		// if our final_ans is ans_f_2, ans_f_3, ans_f_5 
		// then increment their counters i.e f2, f3, f5
		if(final_ans == ans_f_2){
			f2++;
		}
		if(final_ans == ans_f_3){
			f3++;
		}
		if(final_ans == ans_f_5){
			f5++;
		}
	} 
	return dp[n];
}

// driver program to check the code
int main() {
	int n;
	cin >> n;
	cout << n << endl;
	cout<< n << "th ugly number is " <<uglyNumber(n) << endl;

	return 0;
}

Output

10
10
10th ugly number is 12