Ugly Numbers 2

Last Updated: May 13, 2022

Introduction

Ugly Numbers here are those numbers that have only ‘2’, ’3’, and ‘5’ as prime factors.

Problems based on ugly numbers are frequently asked in Paytm, Goldman Sachs and many product-based companies.

Today in this article, we will discuss the solution of a problem - Ugly Numbers 2.

Let’s understand the problem statement more precisely in the next section.

Problem Statement

Given an integer n. Find the nth Ugly Number.

Note: Ugly Numbers have only ‘2’, ’3’, and ‘5’ as prime factors.

Example

Suppose the given integer n = 10.

Input: n=10

Output: 12

Explanation

First 10 Ugly Numbers are [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] .

So the 10th ugly number is 12.

Before proceeding with the solution, it is recommended that you run it through CodeStudio on your own.

Solution Approach

One evident naive approach is to check for each number if it is Ugly or not until we reach the nth ugly number. Most numbers are not Ugly, and thus this approach would be inefficient.

Thus we can divert our approach to generate only the Ugly numbers.

The Ugly number should be of the form (2^a) * (3^b) *( 5^c) where a,b, and c >=0. Therefore a bigger Ugly number can be obtained from smaller Ugly numbers by multiplying either 2,3 or 5. The trick is to keep the Ugly numbers in order.

Keeping in mind the above definitions, we have the following two conditions to satisfy:

  1. We need to create an array of ugly numbers, say dp, where dp[i] denotes (i+1)th ugly number.
  2. The ugly number dp[i] must be derived from a previous ugly number multiplied by either 2, 3, or 5.

For example, 9 is derived from 3 x 3, where 3 is an ugly number.

  1. Also, the ugly number dp[i] may not always be derived from dp[i-1].

For example- Ugly number 8 is derived from 4 x 2 (or 2 x 4) and not from its previous ugly number 6.

 

So here comes Dynamic Programming in action.

Algorithm:

  1. Initialize an array of ugly numbers called ugly_arr of size n and initialize dp[0]=1.
  2. Also, create three integer pointers say p2,p3, and p5, to track the index of the last ugly number to produce the next ugly number.
  3. Initialize a loop of n iterations and at each iteration select a minimum of ‘dp[p2] * 2’, ‘dp[p3] * 3’ and ‘dp[p5] * 5’ and add it at the end of the dp array.
  4. Now Every time we get the newest ugly number, we update the dp array.
  5. Now update the integer pointers, which correspond to the minimum value.
  6. When there is more than one minimum value, remember to update all the corresponding pointers.
  7. Finally return dp[n-1].

 

Let’s see the C++ implementation of the above approach to get a better understanding.

Code:

#include <iostream>
using namespace std;
int nthUgly(int n) 

    int dp[n]; // To store ugly numbers 
    int p2 = 0, p3 = 0, p5 = 0;
    int next_ugly;
 
    dp[0] = 1
    for (int i=1; i<n; i++) 
    { 

next_ugly = min(dp[p2] * 2, min(dp[p3] * 3, dp[p5] * 5)); 
dp[i] = next_ugly; 
if (next_ugly == dp[p2]*2)
p2 = p2+1
if(next_ugly == dp[p3]*3)
p3 = p3+1;
if(next_ugly == dp[p5]*5)
p5 = p5+1;
    } 
    return dp[n-1]; 

 
 
int main() 

    int n=10;
    cout<<nthUgly(n)<<endl;
    return 0
}

 

Output:

12

Complexity Analysis

Time Complexity- O(N), where ‘N’ is the Nth ugly number.

Reason: Since we are iterating until we find the nth Ugly Number, and for each iteration, only performing a constant amount of work ( O(1) ). 

Space Complexity- O(N).

Reason: That’s because we declared an array of size ‘N.’
 

Are you looking for a Roadmap to master Dynamic Programming?

Watch one of the best videos on How to Master Dynamic Programming by Parikh Jain, co-founder of Coding Ninjas.

Frequently Asked Questions

1. What is an Ugly Number?

Any number that can be represented in the form (2^a) * (3^b) *( 5^c) where a,b, and c >=0.

2. What is the time and space complexity of finding nth-Ugly numbers using a dynamic programming approach?

Time complexity is O(n)

Space complexity is O(n)

3. Why do you need an array for ugly numbers?

We need an array because the current ugly number not only depends on the previous ugly number, it can depend on any ugly number previous to the current ugly number.

4. Where can I submit my “Nth-Ugly Number” code?

You can submit your code on CodeStudio and get it accepted here right away.

Key Takeaways

Here we learned one of the most fundamental yet powerful concepts about programming based on mathematics called dynamic programming. We talked about ugly numbers here. 

You can study more about Dynamic Programming by visiting our blog, ‘Dynamic Programming and Algorithms.’

If you wish to practice questions based on Dynamic Programming, you can visit Top Dynamic Programming Questions.

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think