Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … shows the first 11 ugly numbers.
how to solve this problem using recursion?
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 10th 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 ith cell represent ith ugly number. Then we will find the answer to ugly number using this dp relation.
Ugly number(i) = minimum of (2ugly number(f2), 3ugly number(f3), 5*ugly number(f5))
Where, f2, f3, f5 are counters for 2, 3, 5 respectively which stores the index for f2th ugly number, f3th ugly number, f5th ugly number.
Then we will store our answer.
Algorithm:
Initializing f2, f3, f5 to maintain f2th ugly number, f3th ugly number and f5th ugly number to 1.
Creating a DP matrix in which ith cell represent ith ugly number.
Start filling the dp matrix from i = 2.
Ugly number(i) = minimum of (2ugly number(f2), 3ugly number(f3), 5*ugly number(f5)).
Finding the answer using above relation and storing it at ith index.
Now, the time complexity of the above code is O(N).
