2
\$\begingroup\$

I am learning Dynamic Programming and tried to solve the nth ugly number problem using it. Here's my code for the problem in Java:

import java.util.HashSet;

public class UglyNum {
    //using DP bottom up
    public static int getUgly(int n) {
        HashSet<Integer> u = new HashSet<>();
        if (n < 6)
            return n;
        for (int i = 1; i < 6; i++) {
            u.add(i);
        }
        int x = 5;
        int i = 6;
        boolean flag;
        while (x < n) {
            flag = false;
            flag = checkContains(i, 2, u, flag);
            if(!flag)
            flag = checkContains(i, 3, u, flag);
            if(!flag)
            flag = checkContains(i, 5, u, flag);
            if (flag) {
                u.add(i);
                x++;
            }
            if (x == n)
                return i;
            i++;
        }
        return -1;
    }


    private static boolean checkContains(int x, int n, HashSet<Integer> u, boolean flag) {
        if (x % n == 0) {
            if (u.contains(x / n))
                return true;
            else
                return false;
        }
        return flag;
    }
    //DP ends here

}

The idea is that a new number, say x, is ugly only if x/2 or x/3 or x/5 is ugly.

I analysed the code wrt the 2 codes given in the GFG site article and here are the results for 100 ugly numbers: enter image description here

The first time (26.3992 ms) is the time using my dynamic programming approach. The other 2 are the ones given on the site. Clearly my program is taking relatively too much time. Can you help me optimise it?

PS: I am aware of the awesome methods to solve the problem but wondering why mine is so slow.

\$\endgroup\$
  • \$\begingroup\$ "Clearly my program is taking too much time" - No, that's not clear at all. What makes you think so? Too much for what? \$\endgroup\$ – superb rain Aug 2 at 11:29
  • \$\begingroup\$ @superbrain it's 8 times more than the GFG DP approach \$\endgroup\$ – Archer Aug 2 at 13:19
  • \$\begingroup\$ But why is that too much? \$\endgroup\$ – superb rain Aug 2 at 13:20
  • \$\begingroup\$ It's relatively high. \$\endgroup\$ – Archer Aug 2 at 13:38
  • 1
    \$\begingroup\$ Well now you make it sound like you're even including the printing time in the time. Can't tell, as you don't show the code. When I run it on repl.it (which is probably slower than your PC), it takes about 2.5 ms. And why shouldn't the non-DP approach be faster? You're only testing small numbers. \$\endgroup\$ – superb rain Aug 2 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.