Ugly number is defined as the number whose prime factors are only 2,3 and 5.
First eleven ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.
Assumption: 1 is the first ugly number.
APPROACH 1
Reader, as shown in figure 1, we first list the multiples of 2, 3 and 5 individually and make a dp array which stores all the ugly numbers. We know that the first ugly number is 1 so we store it in the array.
Now to find the next ugly numbers, we need to find the valid candidates. We consider the first multiples of 2, 3 and 5 as the valid candidates. Hence, our next ugly number will be the minimum of all the candidates which is 2.
Since 2 has already been used up, we don't use it again. Now the valid candidates for the next ugly number will be the second multiple of 2 i.e. 4 and the previous two candidates, 3 and 5. We choose the minimum out of 4, 3 and 5 which is 3 and store it in the dp array.
This process keeps repeating.
When we reach a situation where the valid candidates are 6, 6 and 10, then we choose 6 as the ugly number and move our pointer forward for the multiples of both 2 and 3
However, on using this approach we reach a situation shown in Figure 5 where the ugly number comes out to be 14. But one of the prime factors of 14 is 7 which is not allowed. An ugly number can only have its prime factors as 2, 3 and 5.
Hence we realize that a number x*n where x=2, 3, 5 is an ugly number only when n also has its factors as 2, 3 and 5.
Here 14=2*7, where x=2 and n=7. Since n=7 doesn't follow the condition of having only 2, 3 and 5 as its factors, therefore it can't be considered as an ugly number.
Reader, in case you have any gaps in your understanding till now, we suggest you watch the solution video.
APPROACH 2
We modify the above process and solve this problem again by using pointers on the dp array.
Initially, all 3 pointers p2, p3 and p5 for the factors 2, 3 and 5 respectively point to the first ugly number 1.
Now we multiply each factor with the ugly number which its corresponding pointer points to.
So, our 3 valid candidates are 2* p2=2, 3*p3=3 and 5*p5=5. We choose the minimum out of these which is 2 as our next ugly number.
Now the pointer to the number which has been already used in the array points to the next ugly number which is 2.
Hence p2 points to the ugly number 2 and p3 and p5 still point to 1.
So, our valid candidates are 2*p2=2*2=4, 3*p3=3*1=3 and 5*p5=5*1=5. We choose the minimum number out of them which is 3.
This process keeps continuing for all the numbers.
Here, the valid candidates are a product of 2 or 3 or 5 and an ugly number (which itself only has the factors 2, 3 and 5). Therefore the product's factors are also only 2, 3 and 5.
So, if we use this approach, we do not face the problem faced in approach 1.
You can also watch the solution video if you have any doubts in this method.
CODE
Reader, if you have understood the above discussion, then you will have no problem in coding this problem yourself.
You can also refer to the code given below which is quite self-explanatory.
import java.io.*;
import java.util.*;
public class Main {
public static int solution(int n) {
int[]dp=new int[n+1];
dp[1]=1;
int p2=1;
int p3=1;
int p5=1;
for(int i=2;i<=n;i++){
int f1=2*dp[p2];
int f2=3*dp[p3];
int f3=5*dp[p5];
int min=Math.min(f1,Math.min(f2,f3));
dp[i]=min;
if(min==f1){
p2++;
}
if(min==f2){
p3++;
}
if(min==f3){
p5++;
}
}
return dp[n];
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
System.out.println(solution(n));
}
}
java;
true";
Analysis
Time Complexity:
O(n)
Space Complexity:
O(n)
We conclude this problem here. We hope it was clear to you.
If you face any difficulties in this problem we suggest you watch its solution video.
