Ugly Numbers - Dynamic Programming

#1

Can you explain how to go about the problem?

#2

hello @adarsh_2001 please read this :
Ugly numbers are those number whose prime factors are 2, 3 or 5.
The ugly-number sequence is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
because every number can only be divided by 2, 3, 5, one way to look at the sequence is to split the sequence to three groups as below:
(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
(3) 1×5, 2×5, 3×5, 4×5, 5×5, …
Then we use similar merge method as merge sort, to get every ugly number from the three subsequence. Every step we choose the smallest one, and move one step after.

So do something like this:

Begin
define array named uglyNum of size n
i2 := 0, i3 := 0, i5 := 0
next2mul := 2, next3mul := 3, next5Mul := 5
next := 1
ugluNum[0] := 1

for i := 1 to n, do
next := minimum of next2Mul, next3Mul and next5Mul
uglyNum[i] := next
if next = next2Mul, then
i2 := i2 + 1
next2mul := uglyNum[i2] x 2
if next = next3Mul, then
i3 := i3 + 1
next3mul := uglyNum[i3] x 3
if next = next5Mul, then
i5 := i5 + 1
next5mul := uglyNum[i5] x 5
done
if you have any doubt you can ask here .

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.