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.
To solve this problem, we need to separate the numbers 1 to n into two groups: prime numbers and non-prime numbers. We can use the Sieve of Eratosthenes to count how many primes are there up to n. Once we know the count of prime numbers, the idea is that those primes must be placed at the prime indices of the permutations. Similarly, non-prime numbers will fill the remaining indices. Therefore, the result will be calculated by multiplying the factorial of the count of prime numbers with the factorial of non-prime numbers.
This Python solution defines a function numPrimeArrangements that calculates the number of valid permutations. It first counts the prime numbers up to n using the count_primes function, which utilizes the Sieve of Eratosthenes algorithm. After determining the number of primes, it calculates the factorials of the number of prime numbers and non-prime numbers, returning their product modulo 10^9 + 7.
Time Complexity: O(n log log n) due to the Sieve of Eratosthenes, plus O(n) for factorials.
Space Complexity: O(n) for the sieve array.
Another approach to solve the problem is to directly check each number from 1 to n whether it is a prime or not. Every time a prime is identified, count it, and once we have the counts for primes and non-primes, use the factorial method to compute the permissible permutations.
This Java solution involves a Solution class with a method numPrimeArrangements, which calculates the number of valid permutations by iterating over numbers from 1 to n to determine how many are prime. The isPrime helper method checks primality using basic trial division. Finally, it calculates the factorial of the counts of primes and non-primes using modulo operation for each multiplication to ensure numerical stability.
Java
JavaScript
Time Complexity: O(n√n) due to the naive primality test iterating √n divisions per number.
Space Complexity: O(1) for the constant space usage.
| Approach | Complexity |
|---|---|
| Prime Counting with Factorials | Time Complexity: O(n log log n) due to the Sieve of Eratosthenes, plus O(n) for factorials. |
| Direct Prime Check with Factorials | Time Complexity: O(n√n) due to the naive primality test iterating √n divisions per number. |
| 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 |
Prime Arrangements | Leetcode #1175 • Techdose • 1,460 views views
Watch 9 more video solutions →Practice Prime Arrangements with our built-in code editor and test cases.
Practice on FleetCode