Counting the Prime Arrangements
- 时间:2020-09-19 10:45:07
- 分类:网络文摘
- 阅读:104 次
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: 682289015Constraints:
1 <= n <= 100Hints:
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) —
推荐阅读:一个整数除以小数是什么含义? 平行四边形、梯形、三角形的高一定要画成虚线吗? 格子乘法介绍 两个因数的末尾一共有几个零,积的末尾就有几个零。 四边形整理和复习思维导图 一些常见数的倍数的特征 什么是集合? 为什么要先乘除后加减 球的体积公式推导证明 生活中的分数
- 评论列表
-
- 添加评论