Leetcode 1175. Prime Arrangements
Explanation: The problem is asking to return the number of permutations of 1 to n such that all prime numbers are at prime indices (1-indexed.) An example will be, if 1 to 5 is given then [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. The answer might be a large number so, the problem asks us to return the answer after mod by 10^9 + 7.
Approach for Solution:
The problem is solved by counting how many prime numbers exist up to n, arranging the prime numbers in the places where the prime positions are, and arranging the non-prime numbers in the non-prime positions.
For example, consider the input n = 5. Two prime numbers exist up to 5 (2 and 3). Repeat the process for non-prime numbers (1, 4 and 5).
Then calculate the factorial of the prime numbers and non-prime numbers using a function and return the multiplication result of both values taken mod by 10^9 + 7.
Let's start coding the solution.
Python Solution
1 2python 3import math 4class Solution: 5 def numPrimeArrangements(self, n: int) -> int: 6 def is_prime(n): 7 if n == 1: return 0 8 for i in range(2, int(n ** 0.5) + 1): 9 if n%i == 0: 10 return 0 11 return 1 12 13 primes = sum([is_prime(i) for i in range(1, n + 1)]) 14 15 return (math.factorial(primes) * math.factorial(n - primes)) % (10 ** 9 + 7)
In the above python code:
-
Firstly, a helper function
is_prime
is defined to make the code simpler. -
Then, the sum of primes till n is calculated.
-
Finally, the factorial of the count of the prime numbers and non-prime numbers is calculated and multiplied together. Because calculation of factorial for large number may result into large output, we take mod of result by
10^9+7
at each step.
Java Solution
1
2java
3class Solution {
4 public int numPrimeArrangements(int n) {
5 long[] primes = new long[n + 1], not_primes = new long[n + 1];
6 primes[1] = not_primes[1] = 1L;
7 int count = 0;
8 long mod = (int)1e9 + 7, prime = 1, not_prime = 1;
9 for (int i = 2; i <= n; i++) {
10 if (isPrime(i)) {
11 prime = prime * ++count % mod;
12 } else {
13 not_prime = not_prime * (i - count) % mod;
14 }
15 }
16 return (int)(prime * not_prime % mod);
17 }
18 private boolean isPrime(int n) {
19 if (n <= 1) { return false; }
20 if (n <= 3) { return true; }
21 if (n % 2 == 0 || n % 3 == 0) { return false; }
22 int sqrtN = (int)Math.sqrt(n)+1;
23 for (long i = 6L; i <= sqrtN; i += 6) {
24 if (n % (i - 1) == 0 || n % (i + 1) == 0) { return false; }
25 }
26 return true;
27 }
28}
In the above Java code:
-
Firstly, a helper function
isPrime
is defined to calculate whether a number is prime (true
) or not (false
). -
Then, assuming the long array
primes
andnot_primes
as 1, and long variablesprime
andnot_prime
as 1. -
Then, if the number
i
is a prime then increment the count of total prime number and calculate its factorial, else calculate the factorial of non-prime numbers. To avoid the integer overflow, the mod is taken at each step. -
Finally, the multiplication of the factorial of the no of prime number and no of non-prime numbers is returned.JavaScript Solution
1
2javascript
3class Solution {
4 constructor() {
5 this.MOD = 1e9 + 7;
6 this.factorials = Array(101).fill(0n);
7 this.factorials[0] = this.factorials[1] = 1n;
8 for (let i = 2; i <= 100; ++i) {
9 this.factorials[i] = this.factorials[i-1] * BigInt(i) % BigInt(this.MOD);
10 }
11 }
12 isPrime(n) {
13 if (n <= 1) {
14 return false;
15 }
16 if (n === 2 || n===3) {
17 return true;
18 }
19 if (n % 2 === 0 || n % 3 === 0) {
20 return false;
21 }
22 for (let i = 5; i * i <= n; i += 6) {
23 if (n % i === 0 || n % (i + 2) === 0) {
24 return false;
25 }
26 }
27 return true;
28 }
29 primeCount(n) {
30 let count = 0;
31 for (let i = 1; i <= n; ++i) {
32 if (this.isPrime(i)) {
33 ++count;
34 }
35 }
36 return count;
37 }
38 numPrimeArrangements(n) {
39 const primeCount = this.primeCount(n);
40 return Number(
41 (this.factorials[primeCount] * this.factorials[n - primeCount])
42 % BigInt(this.MOD)
43 );
44 }
45}
In the above JavaScript code:
-
Firstly, a class
Solution
with the constructor is designed to calculate the factorial of the numbers from 1 to 100 and stored in an arrayfactorials
. -
isPrime
andprimeCount
functions are implemented in the same way as previous solutions to determine if a number is prime and count the prime numbers respectively. -
Then in
numPrimeArrangements
, it takesn
as an argument. The prime number count is calculated and then the factorial is fetched from the precalculated array for both prime and non-prime numbers. -
Finally, the product of these factorials is returned after taking modulo
this.MOD
to maintain the result within javascript's maximum integer (Number.MAX_SAFE_INTEGER
), and also to meet the problem's requirement. The BigInt is used, as the numbers dealing here can be really large. The returned result is then converted back to a Number data type according to the problem's need.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.