Need help in approach of problem

#1

please elaborate how to approach

#2

hi @ksalokya
Dynamic Programming can be applied to this if we can formulate Ugly(n) in terms of Ugly(k) where k < n

If we have k ugly numbers already, then the k+1 ugly number has to be some multiple of the previous ugly numbers only else it would not remain ugly.

We need to multiply previous ugly numbers by 2,3 and 5 and choose the next highest.

But if we multiply all the previous numbers by 2,3 and 5 then it will become thrice O(n2) operations to find all such multiples and then another O(n) operations to find the minimum among them.

To optimize, we will keep track where last multiple of each (2,3,5) was kept.

If we know that, then we need not consider ugly numbers previous to those.

refer this code --> https://ide.codingblocks.com/s/642025

#3

got it, thanks a lot

#4

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.