🥇 Beats 100% | Java, C++, Python | Explanation
TL;DR\njava []\nclass Solution {\n    private static boolean isPrime(int n) {\n        for (int i = 2; i <= n / 2; i++) {\n            if (n % i == 0) return fa
# TL;DR\n``` java []\nclass Solution {\n    private static boolean isPrime(int n) {\n        for (int i = 2; i <= n / 2; i++) {\n            if (n % i == 0) return false;\n        }\n        return true;\n    }\n\n    private static long factorial(int n, long mod) {\n        long f = 1;\n        for (int i = 2; i <= n; i++) {\n            f = (f * i) % mod;\n        }\n        return f;\n    }\n\n    public int numPrimeArrangements(int n) {\n        int mod = (int) 1e9 + 7;\n        int count = 0;\n        for (int i = 2; i <= n; i++) {\n            if (isPrime(i)) count++;\n        }\n        return (int) ((factorial(count, mod) * factorial(n - count, mod)) % mod);\n    }\n}\n```\n``` cpp []\nclass Solution {\nprivate:\n    bool isPrime(int n) {\n        for (int i = 2; i <= n / 2; i++) {\n            if (n % i == 0) return false;\n        }\n        return true;\n    }\n\n    long long factorial(int n, long long mod) {\n        long long f = 1;\n        for (int i = 2; i <= n; i++) {\n            f = (f * i) % mod;\n        }\n        return f;\n    }\n\npublic:\n    int numPrimeArrangements(int n) {\n        const int mod = 1000000007;\n        int count = 0;\n        for (int i = 2; i <= n; i++) {\n            if (isPrime(i)) count++;\n        }\n        return (factorial(count, mod) * factorial(n - count, mod)) % mod;\n    }\n};\n\n```\n``` python []\nclass Solution:\n    def isPrime(self, n: int) -> bool:\n        for i in range(2, n // 2 + 1):\n            if n % i == 0:\n                return False\n        return True\n\n    def factorial(self, n: int, mod: int) -> int:\n        f = 1\n        for i in range(2, n + 1):\n            f = (f * i) % mod\n        return f\n\n    def numPrimeArrangements(self, n: int) -> int:\n        mod = 10 ** 9 + 7\n        count = 0\n        for i in range(2, n + 1):\n            if self.isPrime(i):\n                count += 1\n        return (self.factorial(count, mod) * self.factorial(n - count, mod)) % mod\n\n```\n\n---\n#### \u26A0\uFE0F Please upvote if you like this solution. \uD83D\uDE43\n---\n\n# Approach\n\nTo solve this problem, we can make use of the properties of permutations and prime numbers.\n\nA permutation is an arrangement of objects in a specific order. The number of permutations of a set of `n` objects is `n!` (n factorial), which is the product of all positive integers less than or equal to `n`. This is because for each position, we can choose from `n` objects, then `n-1` for the next position, and so on.\n\nWe start by determining the number of prime numbers within `n`. We can count the prime numbers using a simple function that checks divisibility.\n\nOnce we know the count of prime numbers (let\'s denote it as `p`), we also know the count of non-prime numbers, which is `n - p`.\n\nNotice that the count of prime indices within `n` is exactly `p`, and the count of non-prime indices is `n - p`.\n\nWe can thus generate `p!` permutations of prime numbers at prime positions and `(n - p)!` permutations of non-prime numbers at non-prime positions. \n\nSince these two sets of positions (prime and non-prime) do not intersect, we can simply multiply these two quantities to get the total number of valid arrangements. \n\n# Complexity \n\n- Time complexity: $$O(n^2)$$\n  \n- Space complexity: $$O(1)$$
['Combinatorics', 'C++', 'Java', 'Python3']