Ugly numbers question doubt

#1

I am not able to get what to do in the question

#2

1 2 3 4 5 6 8 9 10 12 15 … so on
If you observe this sequence carefully,

  1. All the numbers in the sequence are in incresing order.

  2. The numbers in the sequence (except 1) are not divisible by any number other than 2,3 or 5.
    This means that the possible prime factors of these numbers are 2,3,or 5.

  3. This sequence must include 1 (though it does not have either of 2,3 or 5 as it’s prime factor.)

You are not required to print this sequence.
You have to print the number at the “nth” position in this sequence, where n is entered by user(input).
Example:
Suppose, n=7
So, the output will be 8
Because 8 is at 7th position in the sequence.

Now, read the question again. This would help you understand it better.

#3

it has to be solved by dp because I am not able to figure the dp approach for this

#4

DP approach:
We have to find the nth ugly number.
In this approach the space complexity is O(n).

An ugly number is one which is divisible by 2,3,or 5 only.
Now, considering them separately,
“1x2,2x2,3x2,4x2,5x2,6x2,8x2,9x2,10x2…”
“1x3,2x3,3x3,4x3,5x3,6x3,8x3,9x3,11x3…”
“1x5,2x5,3x5,4x5,5x5,6x5,8x5,9x5,11x5…”
These are also ugly number sequence.

Now, try to calculate these numbers(considering all three sequences) in increasing order to obtain the desired ugly sequence.
Then, print the nth ugly number.

Steps:
1 Declare an array to store (actual sequence) ugly numbers: ug[n]
2 Initialize the first ugly no: ugly[0] = 1
3 Initialize three array of index variables i2, i3, i5 (for calculating the values of above mentioned sequences) to point to
1st element of the ugly array:
i2 = i3 = i5 =0;
4 Initialize 3 choices for the next ugly no:
next_mulitple_of_2 = ugly[i2]*2;
next_mulitple_of_3 = ugly[i3]*3
next_mulitple_of_5 = ugly[i5]*5;
//we are finding the first number of each sequence.
5 Now go in a loop to fill all ugly numbers till n:
For (i = 1; i < n; i++ )
{
//find the minimum of three
next_ugly_no = Min(next_mulitple_of_2,
next_mulitple_of_3,
next_mulitple_of_5);

ugly[i] =  next_ugly_no       

if (next_ugly_no  == next_mulitple_of_2) 
{             
    i2 = i2 + 1;        
    next_mulitple_of_2 = ugly[i2]*2;
} 
if (next_ugly_no  == next_mulitple_of_3) 
{             
    i3 = i3 + 1;        
    next_mulitple_of_3 = ugly[i3]*3;
 }            
 if (next_ugly_no  == next_mulitple_of_5)
 {    
    i5 = i5 + 1;        
    next_mulitple_of_5 = ugly[i5]*5;
 }

}/* end of for loop */
6.print the nth ugly number

#5

Oh got it , its kind of the sieve technique

#6

I am glad, you found that useful. Please mark your doubt as resolved and if possible, give a like and review about me.