Ugly Numbers Problem

#1

help me in approaching this problem, plz

#2

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.

So start with

        long next_multiple_of_2 = 2;
        long next_multiple_of_3 = 3;
        long next_multiple_of_5 = 5;
        long next_ugly_no=1;

and then run a loop

        for (int i = 1; i < n; i++) {
            next_ugly_no = Math.min(next_multiple_of_2, Math.min(next_multiple_of_3, next_multiple_of_5));
            dp[i]=next_ugly_no;
            if(next_multiple_of_2==next_ugly_no) {
                i2++;
                next_multiple_of_2=dp[i2]*2;
            }
            if(next_multiple_of_3==next_ugly_no) {
                i3++;
                next_multiple_of_3=dp[i3]*3;
            }
            if(next_multiple_of_5==next_ugly_no) {
                i5++;
                next_multiple_of_5=dp[i5]*5;
            }
        }