🤢 Ugly Numbers

darpanjbora · darpanjbora · commit 46f1f50fe259 · 2018-05-31T23:17:29.000+05:30
diff --git a/Dynamic Programming/UglyNumbers.java b/Dynamic Programming/UglyNumbers.java
@@ -0,0 +1,49 @@
+/**
+ * Ugly numbers are numbers whose only prime factors are 2, 3 or 5.
+ */
+
+import java.util.*;
+import java.io.*;
+
+class UglyNumbers {
+
+    public static int getNthUglyNumber(int n) {
+        int array[] = new int[n + 1];
+        
+        array[0] = 1;
+
+        int i2 = 0;
+        int i3 = 0;
+        int i5 = 0;
+
+        int nextMultipleOf2 = 2;
+        int nextMultipleOf3 = 3;
+        int nextMultipleOf5 = 5;
+
+        
+        for (int i = 1; i < n; i++) {
+
+             int min = Math.min(nextMultipleOf2, Math.min(nextMultipleOf3, nextMultipleOf5));
+
+            array[i] = min;
+            if (min == nextMultipleOf2) {
+                i2++;
+                nextMultipleOf2 = array[i2]*2; 
+            }
+            if (min == nextMultipleOf3) {
+                i3++;
+                nextMultipleOf3 = array[i3]*3; 
+            }
+            if (min == nextMultipleOf5) {
+                i5++;
+                nextMultipleOf5 = array[i5]*5; 
+            }
+        }
+        return array[n-1];
+    }
+
+    public static void main(String[] args) {
+        int n = 150;
+        System.out.println(getNthUglyNumber(n));
+    }
+}
