Counting the Prime Arrangements

  • 时间:2020-09-19 10:45:07
  • 分类:网络文摘
  • 阅读:107 次

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) —

推荐阅读:
数学题:东西南北两条路交叉成直角  数学题:哥哥和弟弟进行100米赛跑  数学题:把14分成若干个自然数的和  数学题:张王李赵刘5人合作完成一项工程  数学题:姐姐8年后的年龄是妹妹3年前的5倍  数学题:一个直角三角形以它的斜边为轴旋转一周  数学题:一个三角形被一个长方形挡住了  摘桃子的数学题  如图平行四边形ABCD的周长为72厘米  每个人都和其他人握了一次手 
评论列表
添加评论