Algorithm
Problem Name: 1175. Prime Arrangements
Problem Link: https://leetcode.com/problems/prime-arrangements/
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
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
function isPrime(n) {
// Corner case
if (n <= 1) return false
// Check from 2 to n-1
for (let i = 2; i < n; i++) if (n % i == 0) return false
return true
}
const numPrimeArrangements = function(n) {
let primes = 0 // # of primes.
let result = 1
const mod = 10 ** 9 + 7
for (let i = 2; i < = n; i++) if (isPrime(i)) primes++
// Calculate factorials and multiply.
for (let i = primes; i >= 1; i--) result = (i * result) % mod
for (let i = n - primes; i >= 1; i--) result = (i * result) % mod
return result // result of multiplying factorial(primes) with factorial(non-primes)
}
Input
n = 5
Output
12
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numPrimeArrangements(self, n: int) -> int:
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
cnt = bisect.bisect(primes, n)
return math.factorial(cnt) * math.factorial(n - cnt) % (10 ** 9 + 7)
Input
n = 5
Output
12
#3 Code Example with C# Programming
Code -
C# Programming
using System.Linq;
namespace LeetCode
{
public class _1175_PrimeArrangements
{
private readonly int MOD = 1000000007;
public int NumPrimeArrangements(int n)
{
var primes = new bool[n + 1];
for (int i = 2; i < = n; i++)
primes[i] = true;
for (int i = 2; i * i < = n; i++)
if (primes[i])
for (int j = i * i; j < = n; j += i)
primes[j] = false;
var primeCount = primes.Count(p => p);
long result = 1;
for (int i = 2; i < = primeCount; i++)
result = (result * i) % MOD;
for (int i = 2; i < = n - primeCount; i++)
result = (result * i) % MOD;
return (int)result;
}
}
}
Input
n = 5
Output
12