In this guide, you will get 1175. Prime Arrangements LeetCode Solution with the best time and space complexity. The solution to Prime Arrangements problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)
(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)
Since the answer may be large, return the answer modulo 10^9 + 7.
Example 1:
Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.
Example 2:
Input: n = 100
Output: 682289015
Constraints:
1 <= n <= 100
Complexity Analysis
Time Complexity:
Space Complexity:
1175. Prime Arrangements LeetCode Solution in C++
class Solution {
public:
int numPrimeArrangements(int n) {
const int count = countPrimes(n);
return factorial(count) * factorial(n - count) % kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
int countPrimes(int n) {
vector<bool> prime(n + 1, true);
prime[0] = false;
prime[1] = false;
for (int i = 0; i <= sqrt(n); ++i)
if (prime[i])
for (int j = i * i; j <= n; j += i)
prime[j] = false;
return ranges::count(prime, true);
}
long factorial(int n) {
long res = 1;
for (int i = 2; i <= n; ++i)
res = res * i % kMod;
return res;
}
}; /* code provided by PROGIEZ */
1175. Prime Arrangements LeetCode Solution in Java
class Solution {
public int numPrimeArrangements(int n) {
final int count = countPrimes(n);
return (int) (factorial(count) * factorial(n - count) % kMod);
}
private static final int kMod = 1_000_000_007;
private int countPrimes(int n) {
boolean[] prime = new boolean[n + 1];
Arrays.fill(prime, 2, n + 1, true);
for (int i = 0; i * i <= n; ++i)
if (prime[i])
for (int j = i * i; j <= n; j += i)
prime[j] = false;
int count = 0;
for (boolean p : prime)
if (p)
++count;
return count;
}
private long factorial(int n) {
long res = 1;
for (int i = 2; i <= n; ++i)
res = res * i % kMod;
return res;
}
} // code provided by PROGIEZ
1175. Prime Arrangements LeetCode Solution in Python
class Solution:
def numPrimeArrangements(self, n: int) -> int:
kMod = 1_000_000_007
def factorial(n: int) -> int:
fact = 1
for i in range(2, n + 1):
fact = fact * i % kMod
return fact
count = self._countPrimes(n)
return factorial(count) * factorial(n - count) % kMod
def _countPrimes(self, n: int) -> int:
isPrime = [False] * 2 + [True] * (n - 1)
for i in range(2, int(n**0.5) + 1):
if isPrime[i]:
for j in range(i * i, n + 1, i):
isPrime[j] = False
return sum(isPrime) # code by PROGIEZ
