Watch 10 video solutions for Prime Arrangements, a easy level problem involving Math. This walkthrough by Techdose has 1,460 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 100Problem Overview: You are given an integer n. Arrange numbers from 1 to n so that prime numbers appear only at prime indices (1-indexed). The task is to count how many valid permutations exist, returning the result modulo 1e9 + 7.
The key observation: only the count of primes matters, not their specific values. If there are p primes ≤ n, then exactly p positions in the permutation are prime indices. Those slots must be filled with the p prime numbers in any order. The remaining n - p non-prime numbers fill the remaining positions.
Approach 1: Prime Counting with Factorials (O(n log log n) time, O(n) space)
First compute how many primes exist up to n. The common method is the Sieve of Eratosthenes, which marks multiples while iterating through numbers up to n. This runs in O(n log log n) time and uses an array of size n. Once you know the number of primes p, the number of valid permutations is simply p! * (n - p)!. Compute factorials using modular multiplication with modulus 1e9 + 7. This approach separates the problem into two clear steps: counting primes and counting permutations. It is efficient and scales comfortably within constraints. This solution relies heavily on concepts from math and prime numbers.
Approach 2: Direct Prime Check with Factorials (O(n√n) time, O(1) extra space)
Instead of building a sieve, iterate from 2 to n and check if each number is prime using trial division up to √x. Increment a counter whenever a prime is found. This avoids maintaining an auxiliary array but increases the runtime to O(n√n). After counting primes, compute p! and (n - p)! under modulo just like the previous approach. This method is straightforward and easy to implement, especially in languages where quick loops are cheap. It uses constant auxiliary space and still performs well because n in this problem is relatively small.
Both approaches rely on the combinatorial insight that permutations of primes and non-primes are independent. The final answer is the product of the factorials of their counts. This is essentially a constrained permutation counting problem, closely related to ideas from combinatorics.
Recommended for interviews: Prime counting with a sieve plus factorial computation. Interviewers expect you to recognize that only the number of primes matters, reducing the permutation problem to p! × (n − p)!. Showing the direct prime check first demonstrates understanding, but the sieve-based counting shows stronger algorithmic awareness and better asymptotic performance.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prime Counting with Sieve + Factorials | O(n log log n) | O(n) | Best general solution when you want efficient prime counting and scalable performance |
| Direct Prime Check + Factorials | O(n√n) | O(1) | Useful when avoiding extra arrays or when constraints are small |