add 1641

fishercoder1534 · fishercoder1534 · commit c365dec0f51d · 2021-01-09T16:52:11.000-08:00
diff --git a/README.md b/README.md
@@ -34,6 +34,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1656|[Design an Ordered Stream](https://leetcode.com/problems/design-an-ordered-stream/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1656.java) ||Easy|Array, Design|
 |1652|[Defuse the Bomb](https://leetcode.com/problems/defuse-the-bomb/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1652.java) ||Easy|Array|
 |1646|[Get Maximum in Generated Array](https://leetcode.com/problems/get-maximum-in-generated-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1646.java) ||Easy|Array|
+|1641|[Count Sorted Vowel Strings](https://leetcode.com/problems/count-sorted-vowel-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1641.java) ||Medium|Math, DP, Backtracking|
 |1640|[Check Array Formation Through Concatenation](https://leetcode.com/problems/check-array-formation-through-concatenation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1640.java) ||Easy|Array, Sort|
 |1637|[Widest Vertical Area Between Two Points Containing No Points](https://leetcode.com/problems/widest-vertical-area-between-two-points-containing-no-points/)|[Javascript](./javascript/_1637.js)| | Medium | Sort |
 |1636|[Sort Array by Increasing Frequency](https://leetcode.com/problems/sort-array-by-increasing-frequency/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1636.java) ||Easy|Array, Sort|
diff --git a/src/main/java/com/fishercoder/solutions/_1641.java b/src/main/java/com/fishercoder/solutions/_1641.java
@@ -0,0 +1,41 @@
+package com.fishercoder.solutions;
+
+import java.util.Arrays;
+
+public class _1641 {
+    public static class Solution1 {
+        /**
+         * I solved this problem using Math, no DP, recursion or backtracking techniques.
+         * Time: beat 100% submission consistently since it's O(n), essentialy it's O(1) because the contraints in the problem state: 1 <= n <= 50
+         * After writing out from n = 1 to 3, we can see the pattern.
+         * Detailed reasoning to be seen in my youtube video on my channel: https://www.youtube.com/fishercoder.
+         */
+        public int countVowelStrings(int n) {
+            if (n == 1) {
+                return 5;
+            }
+            int[] arr = new int[]{1, 1, 1, 1, 1};
+            int sum = 5;
+            for (int i = 2; i <= n; i++) {
+                int[] copy = new int[5];
+                for (int j = 0; j < arr.length; j++) {
+                    if (j == 0) {
+                        copy[j] = sum;
+                    } else {
+                        copy[j] = copy[j - 1] - arr[j - 1];
+                    }
+                }
+                arr = Arrays.copyOf(copy, 5);
+                sum = 0;
+                for (int j = 0; j < arr.length; j++) {
+                    sum += arr[j];
+                }
+            }
+            sum = 0;
+            for (int j = 0; j < arr.length; j++) {
+                sum += arr[j];
+            }
+            return sum;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1641Test.java b/src/test/java/com/fishercoder/_1641Test.java
@@ -0,0 +1,42 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1641;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1641Test {
+    private static _1641.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1641.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(5, solution1.countVowelStrings(1));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals(15, solution1.countVowelStrings(2));
+    }
+
+    @Test
+    public void test3() {
+        assertEquals(35, solution1.countVowelStrings(3));
+    }
+
+    @Test
+    public void test4() {
+        assertEquals(70, solution1.countVowelStrings(4));
+    }
+
+    @Test
+    public void test5() {
+        assertEquals(66045, solution1.countVowelStrings(33));
+    }
+
+}
