1175. Prime Arrangements #

Problem #

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

Problem Summary #

Please help design arrangements for the numbers from 1 to n such that all “prime numbers” should be placed at “prime indices” (indices start from 1); you need to return the total number of possible arrangements. Let’s review what a “prime number” is: a prime number must be greater than 1 and cannot be represented as the product of two positive integers smaller than itself. Since the answer may be very large, you only need to return the result after taking the answer modulo 10^9 + 7.

Note:

• 1 <= n <= 100

Solution Approach #

• Given a number n, find the number of permutations of the n numbers from 1 to n such that prime numbers are at prime index positions.
• Since n in this problem is less than 100, we can use a lookup table. First list all prime numbers less than 100 in a table. Then compute the permutation count for the primes less than or equal to n, namely c!, and then compute the permutation count for the remaining non-primes, namely (n-c)!. The product of the two is the final answer.

Code #

package leetcode

import "sort"

var primes = []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

func numPrimeArrangements(n int) int {
	primeCount := sort.Search(25, func(i int) bool { return primes[i] > n })
	return factorial(primeCount) * factorial(n-primeCount) % 1000000007
}

func factorial(n int) int {
	if n == 1 || n == 0 {
		return 1
	}
	return n * factorial(n-1) % 1000000007
}