add 1175

fishercoder1534 · fishercoder1534 · commit a9fd6972626d · 2020-12-30T09:18:54.000-08:00
diff --git a/README.md b/README.md
@@ -235,7 +235,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1182|[Shortest Distance to Target Color](https://leetcode.com/problems/shortest-distance-to-target-color/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1182.java) ||Medium|Binary Search|
 |1180|[Count Substrings with Only One Distinct Letter](https://leetcode.com/problems/count-substrings-with-only-one-distinct-letter/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1180.java) | |Easy|Math, String|
 |1176|[Diet Plan Performance](https://leetcode.com/problems/diet-plan-performance/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1176.java) | |Easy|Array, Sliding Window|
-|1175|[Prime Arrangements](https://leetcode.com/problems/prime-arrangements/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1175.java) | |Easy||
+|1175|[Prime Arrangements](https://leetcode.com/problems/prime-arrangements/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1175.java) | |Easy|Math|
 |1165|[Single-Row Keyboard](https://leetcode.com/problems/single-row-keyboard/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1165.java) | |Easy||
 |1161|[Maximum Level Sum of a Binary Tree](https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1161.java) | |Medium|Graph|
 |1160|[Find Words That Can Be Formed by Characters](https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1160.java)| |Easy||
diff --git a/src/main/java/com/fishercoder/solutions/_1175.java b/src/main/java/com/fishercoder/solutions/_1175.java
@@ -1,10 +1,46 @@
 package com.fishercoder.solutions;
 
+import java.math.BigInteger;
+import java.util.Arrays;
+
 public class _1175 {
     public static class Solution1 {
-        public int numPrimeArrangements(int n) {
-            //TODO: implement it
-            return -1;
+        //credit: https://leetcode.com/problems/prime-arrangements/discuss/371884/Simple-Java-With-comment-sieve_of_eratosthenes
+        static int MOD = 1000000007;
+
+        public static int numPrimeArrangements(int n) {
+            int numberOfPrimes = generatePrimes(n);
+            BigInteger x = factorial(numberOfPrimes);
+            BigInteger y = factorial(n - numberOfPrimes);
+            return x.multiply(y).mod(BigInteger.valueOf(MOD)).intValue();
+        }
+
+        public static BigInteger factorial(int n) {
+            BigInteger fac = BigInteger.ONE;
+            for (int i = 2; i <= n; i++) {
+                fac = fac.multiply(BigInteger.valueOf(i));
+            }
+            return fac.mod(BigInteger.valueOf(MOD));
+        }
+
+        public static int generatePrimes(int n) {
+            boolean[] prime = new boolean[n + 1];
+            Arrays.fill(prime, 2, n + 1, true);
+            for (int i = 2; i * i <= n; i++) {
+                if (prime[i]) {
+                    for (int j = i * i; j <= n; j += i) {
+                        prime[j] = false;
+                    }
+                }
+            }
+            int count = 0;
+            for (int i = 0; i < prime.length; i++) {
+                if (prime[i]) {
+                    count++;
+                }
+            }
+
+            return count;
         }
     }
 }
