add a solution for 264

fishercoder1534 · fishercoder1534 · commit 08561749a2b7 · 2021-11-08T07:10:20.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_264.java b/src/main/java/com/fishercoder/solutions/_264.java
@@ -1,5 +1,7 @@
 package com.fishercoder.solutions;
 
+import java.util.TreeSet;
+
 public class _264 {
 
     public static class Solution1 {
@@ -31,4 +33,40 @@ public int nthUglyNumber(int n) {
             return ugly[n - 1];
         }
     }
+
+    public static class Solution2 {
+        /**
+         * My completely original solution on 11/7/2021.
+         * Although not super robust, as the input increases, I'll have to increase the times (variable n) on line 61 as some smaller numbers might appear later.
+         */
+        public int nthUglyNumber(int n) {
+            TreeSet<Long> treeSet = new TreeSet<>();
+            treeSet.add(1l);
+            int count = 1;
+            int polled = 0;
+            int[] primes = new int[]{2, 3, 5};
+            while (!treeSet.isEmpty()) {
+                int size = treeSet.size();
+                for (int i = 0; i < size; i++) {
+                    Long curr = treeSet.pollFirst();
+                    polled++;
+                    if (polled == n) {
+                        return curr.intValue();
+                    }
+                    for (int prime : primes) {
+                        treeSet.add(prime * curr);
+                        count++;
+                    }
+                }
+                if (count >= n * 3) {
+                    while (polled < n - 1) {
+                        treeSet.pollFirst();
+                        polled++;
+                    }
+                    return treeSet.pollFirst().intValue();
+                }
+            }
+            return -1;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_264Test.java b/src/test/java/com/fishercoder/_264Test.java
@@ -8,19 +8,59 @@
 
 public class _264Test {
     private static _264.Solution1 solution1;
+    private static _264.Solution2 solution2;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _264.Solution1();
+        solution2 = new _264.Solution2();
     }
 
     @Test
     public void test1() {
         assertEquals(12, solution1.nthUglyNumber(10));
+        assertEquals(12, solution2.nthUglyNumber(10));
     }
 
     @Test
     public void test2() {
         assertEquals(402653184, solution1.nthUglyNumber(1352));
+        assertEquals(402653184, solution2.nthUglyNumber(1352));
+    }
+
+    @Test
+    public void test3() {
+        assertEquals(1, solution1.nthUglyNumber(1));
+        assertEquals(1, solution2.nthUglyNumber(1));
+    }
+
+    @Test
+    public void test4() {
+        assertEquals(2, solution1.nthUglyNumber(2));
+        assertEquals(2, solution2.nthUglyNumber(2));
+    }
+
+    @Test
+    public void test5() {
+        assertEquals(3, solution1.nthUglyNumber(3));
+        assertEquals(3, solution2.nthUglyNumber(3));
+    }
+
+    @Test
+    public void test6() {
+        assertEquals(5, solution1.nthUglyNumber(5));
+        assertEquals(5, solution2.nthUglyNumber(5));
+    }
+
+    @Test
+    public void test7() {
+        assertEquals(3888, solution1.nthUglyNumber(134));
+        assertEquals(3888, solution2.nthUglyNumber(134));
+    }
+
+    @Test
+    public void test8() {
+        assertEquals(536870912, solution1.nthUglyNumber(1407));
+        assertEquals(536870912, solution2.nthUglyNumber(1407));
     }
 }
