Counting the 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

Hints:
Solve the problem for prime numbers and composite numbers separately.
Multiply the number of permutations of prime numbers over prime indices with the number of permutations of composite numbers over composite indices.
The number of permutations equals the factorial.

Counting Prime Numbers and Composite Numbers

The number of permutations will be equal to the product of the permutation from all prime numbers and the number of composite numbers. And the total permutations for n-numbers can be computed via factorial which is n!

We can use Sieve Prime Algorithms to generate the prime numbers less than 100 (given constraints) quickly – and use a boolean array to indicate if a number is prime or not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
public:
    int numPrimeArrangements(int n) {
        countPrimes();
        int numOfPrimes = 0;
        for (int i = 1; i <= n; ++ i) {
            if (primes[i]) {
                numOfPrimes ++;
            }
        }
        return ((int64_t)(fact(numOfPrimes) % MOD) * 
                (fact(n - numOfPrimes) % MOD)) % MOD;
    }
private:
    const int MOD = (int)(1e9 + 7);
    static const int MAXN = 101;
    bool primes[MAXN];
    
    void countPrimes() { // using Sieve Prime Algorithms
        std::fill(begin(primes), end(primes), true);
        primes[0] = false;
        primes[1] = false;        
        int i = 2;
        while (i < MAXN) {            
            int j = i;
            while (j + i < MAXN) {
                j += i;
                primes[j] = false;
            }
            i ++;
            while ((i < MAXN) && (!primes[i])) i ++;            
        }
    }
    
    int fact(int n) {
        int64_t r = 1;
        for (int i = 2; i <= n; ++ i) {
            r = ((r % MOD) * (i % MOD)) % MOD;
        }
        return (int)r;
    }
};

class Solution {
public:
    int numPrimeArrangements(int n) {
        countPrimes();
        int numOfPrimes = 0;
        for (int i = 1; i <= n; ++ i) {
            if (primes[i]) {
                numOfPrimes ++;
            }
        }
        return ((int64_t)(fact(numOfPrimes) % MOD) * 
                (fact(n - numOfPrimes) % MOD)) % MOD;
    }
private:
    const int MOD = (int)(1e9 + 7);
    static const int MAXN = 101;
    bool primes[MAXN];
    
    void countPrimes() { // using Sieve Prime Algorithms
        std::fill(begin(primes), end(primes), true);
        primes[0] = false;
        primes[1] = false;        
        int i = 2;
        while (i < MAXN) {            
            int j = i;
            while (j + i < MAXN) {
                j += i;
                primes[j] = false;
            }
            i ++;
            while ((i < MAXN) && (!primes[i])) i ++;            
        }
    }
    
    int fact(int n) {
        int64_t r = 1;
        for (int i = 2; i <= n; ++ i) {
            r = ((r % MOD) * (i % MOD)) % MOD;
        }
        return (int)r;
    }
};

Alternatively, we can test each number on the fly – O(Sqrt(N)) complexity – but O(1) particularly in this problem given the constraint of maximum input is 100.

1
2
3
4
5
6
7
8
9

bool checkPrime(int n) { // O(Sqrt(N))
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

bool checkPrime(int n) { // O(Sqrt(N))
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

–EOF (The Ultimate Computing & Technology Blog) —