Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
2.2.
Explanation
3.
Solution Approach
3.1.
Algorithm:
4.
Code:
4.1.
Complexity Analysis
4.1.1.
Time Complexity- O(N), where ‘N’ is the Nth ugly number.
4.1.2.
Space Complexity- O(N).
5.
Frequently Asked Questions
6.
Key Takeaways
Last Updated: Mar 27, 2024

Ugly Numbers 2

Author
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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.

Also checkout,  Euclid GCD Algorithm

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 Coding Ninjas Studio on your own.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 Coding Ninjas Studio and get it accepted here right away.

Also Read - Strong number in c

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.

Check out this problem - Frog Jump

Previous article
Total Hamming Distance
Next article
Find Elements
Live masterclass