# Ugly Number problem using dynamic programming

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++) {
}
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) {
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:

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.

• "Clearly my program is taking too much time" - No, that's not clear at all. What makes you think so? Too much for what? – superb rain Aug 2 at 11:29
• @superbrain it's 8 times more than the GFG DP approach – Archer Aug 2 at 13:19
• But why is that too much? – superb rain Aug 2 at 13:20
• It's relatively high. – Archer Aug 2 at 13:38
• 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. – superb rain Aug 2 at 14:29