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 and not_primes as 1, and long variables prime and not_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 array factorials.

• isPrime and primeCount 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 takes n 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.