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.
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:
We need to create an array of ugly numbers, say dp, where dp[i] denotes (i+1)th ugly number.
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.
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:
Initialize an array of ugly numbers called ugly_arr of size n and initialize dp[0]=1.
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.
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.
Now Every time we get the newest ugly number, we update the dp array.
Now update the integer pointers, which correspond to the minimum value.
When there is more than one minimum value, remember to update all the corresponding pointers.
Finally return dp[n-1].
Let’s see the C++ implementation of the above approach to get a better understanding.
Code:
#include <iostream> usingnamespacestd; intnthUgly(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++) {
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.
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.
85+ registered