Prime Arrangements
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach improves upon the brute-force method by using a more efficient primality test. The overall logic of counting primes, calculating factorials, and combining the results remains the same. The key optimization is in how we determine if a number is prime.
Algorithm
- Initialize
primeCountto 0. - Iterate from
i = 1ton. - For each
i, check if it's a prime number using an optimized primality test (checking divisibility from 2 tosqrt(i)). - If
iis prime, incrementprimeCount. - Calculate
nonPrimeCount = n - primeCount. - Calculate
factorial(primeCount)andfactorial(nonPrimeCount)modulo10^9 + 7. - Return the product of the two factorials modulo
10^9 + 7.
Walkthrough
The core improvement lies in the isPrime function. A number x is not prime if it has a divisor other than 1 and itself. If x has a divisor d, then x = d * (x/d). One of these factors must be less than or equal to sqrt(x). Therefore, to check if x is prime, we only need to check for divisibility by numbers from 2 up to sqrt(x). This significantly reduces the number of checks compared to the naive approach.
The rest of the algorithm is identical:
- Count the number of primes up to
nusing the optimizedisPrimefunction. - Calculate
primeCountandnonPrimeCount. - Compute
(primeCount!) * ((n - primeCount)!)modulo10^9 + 7.
class Solution { public int numPrimeArrangements(int n) { long MOD = 1_000_000_007; int primeCount = 0; for (int i = 1; i <= n; i++) { if (isOptimizedPrime(i)) { primeCount++; } } int nonPrimeCount = n - primeCount; long ans = factorial(primeCount, MOD); ans = (ans * factorial(nonPrimeCount, MOD)) % MOD; return (int) ans; } private boolean isOptimizedPrime(int num) { if (num <= 1) { return false; } for (int i = 2; i * i <= num; i++) { if (num % i == 0) { return false; } } return true; } private long factorial(int k, long MOD) { long res = 1; for (int i = 2; i <= k; i++) { res = (res * i) % MOD; } return res; }}Complexity
Time
O(n * sqrt(n)). We iterate `n` times, and each primality test takes up to O(sqrt(n)) time.
Space
O(1). No extra space proportional to `n` is used.
Trade-offs
Pros
More efficient than the naive approach.
Still relatively simple to implement and requires no extra space.
Cons
While better than the naive approach, it is still not the most optimal method for finding all primes up to
n.
This is the most efficient approach for this problem, especially if n were larger. It uses the Sieve of Eratosthenes algorithm to find all prime numbers up to n in a highly optimized manner before proceeding with the factorial calculations.
Algorithm
- Create a boolean array
isPrimeof sizen+1and initialize it totrue. - Run the Sieve of Eratosthenes algorithm on this array to mark all non-prime numbers up to
n. - Count the number of
truevalues inisPrimefrom index 2 tonto getprimeCount. - Calculate
nonPrimeCount = n - primeCount. - Calculate
factorial(primeCount)andfactorial(nonPrimeCount)modulo10^9 + 7. - Return the product of the two factorials modulo
10^9 + 7.
Walkthrough
The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a specified integer. It works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2.
The algorithm proceeds as follows:
- Create a boolean array
isPrimeof sizen+1and initialize all entries totrue. A valueisPrime[i]will befalseifiis not a prime,trueotherwise. MarkisPrime[0]andisPrime[1]asfalse. - Iterate from
p = 2up tosqrt(n). - If
isPrime[p]istrue(meaningpis a prime), then iterate through all multiples ofp(starting fromp*p) and mark them asfalse.
After the sieve has run, we can count the number of primes (primeCount) by simply iterating through the isPrime array from 2 to n and counting the true values. Once primeCount is known, the rest of the logic is the same: calculate (primeCount!) * ((n - primeCount)!) modulo 10^9 + 7.
class Solution { public int numPrimeArrangements(int n) { long MOD = 1_000_000_007; // Step 1: Find prime count using Sieve of Eratosthenes boolean[] isPrime = new boolean[n + 1]; java.util.Arrays.fill(isPrime, true); if (n >= 0) isPrime[0] = false; if (n >= 1) isPrime[1] = false; for (int p = 2; p * p <= n; p++) { if (isPrime[p]) { for (int i = p * p; i <= n; i += p) { isPrime[i] = false; } } } int primeCount = 0; for (int i = 2; i <= n; i++) { if (isPrime[i]) { primeCount++; } } // Step 2: Calculate factorials int nonPrimeCount = n - primeCount; long ans = factorial(primeCount, MOD); ans = (ans * factorial(nonPrimeCount, MOD)) % MOD; return (int) ans; } private long factorial(int k, long MOD) { long res = 1; for (int i = 2; i <= k; i++) { res = (res * i) % MOD; } return res; }}Complexity
Time
O(n * log(log(n))). The Sieve algorithm is the dominant part. The subsequent counting and factorial calculations take O(n), which is less significant.
Space
O(n). We need a boolean array of size `n+1` for the sieve.
Trade-offs
Pros
The most time-efficient method for finding all primes in a given range.
Optimal for problems where prime numbers in a range need to be identified multiple times or in bulk.
Cons
Uses extra space proportional to
nfor the sieve array.Slightly more complex to implement than trial division methods.
This approach directly implements the mathematical formula derived from the problem's constraints. The core idea is to separate the numbers and indices into two groups: prime and non-prime. The number of valid permutations is the product of the permutations of primes within prime indices and the permutations of non-primes within non-prime indices. It uses a simple, but inefficient, method to check for prime numbers.
Algorithm
- Initialize
primeCountto 0. - Iterate from
i = 1ton. - For each
i, check if it's a prime number using a naive primality test (checking divisibility from 2 toi-1). - If
iis prime, incrementprimeCount. - Calculate
nonPrimeCount = n - primeCount. - Calculate
factorial(primeCount)modulo10^9 + 7. - Calculate
factorial(nonPrimeCount)modulo10^9 + 7. - The result is the product of the two factorials, also taken modulo
10^9 + 7.
Walkthrough
First, we need to determine the number of prime numbers between 1 and n. Let's call this primeCount. We can find primeCount by iterating through each number i from 2 to n and checking if it's prime. A naive primality test for a number x involves checking for divisibility by all integers from 2 up to x-1.
The number of non-prime numbers will be n - primeCount. The problem now reduces to arranging primeCount prime numbers in primeCount available prime-indexed slots, and n - primeCount non-prime numbers in the remaining n - primeCount non-prime-indexed slots.
The number of ways to arrange k items is k! (k factorial). Therefore, the total number of valid permutations is (primeCount!) * ((n - primeCount)!). Since the result can be very large, all calculations, especially the factorials, must be performed modulo 10^9 + 7. We calculate the factorials iteratively, applying the modulo at each multiplication step to prevent overflow.
class Solution { public int numPrimeArrangements(int n) { long MOD = 1_000_000_007; int primeCount = 0; for (int i = 1; i <= n; i++) { if (isNaivePrime(i)) { primeCount++; } } int nonPrimeCount = n - primeCount; long ans = factorial(primeCount, MOD); ans = (ans * factorial(nonPrimeCount, MOD)) % MOD; return (int) ans; } private boolean isNaivePrime(int num) { if (num <= 1) { return false; } for (int i = 2; i < num; i++) { if (num % i == 0) { return false; } } return true; } private long factorial(int k, long MOD) { long res = 1; for (int i = 2; i <= k; i++) { res = (res * i) % MOD; } return res; }}Complexity
Time
O(n^2). The primality test for each number up to `n` takes O(n) time, and we do this for `n` numbers. The factorial calculations take O(n) time, which is dominated by the prime counting part.
Space
O(1). We only use a few variables to store counts and intermediate results.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space.
Cons
The primality test is very inefficient, with a time complexity of O(n) for each number.
Overall time complexity is poor and would be too slow for larger values of
n.
Solutions
Solution
class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int numPrimeArrangements ( int n ) { int cnt = count ( n ); long ans = f ( cnt ) * f ( n - cnt ); return ( int ) ( ans % MOD ); } private long f ( int n ) { long ans = 1 ; for ( int i = 2 ; i <= n ; ++ i ) { ans = ( ans * i ) % MOD ; } return ans ; } private int count ( int n ) { int cnt = 0 ; boolean [] primes = new boolean [ n + 1 ]; Arrays . fill ( primes , true ); for ( int i = 2 ; i <= n ; ++ i ) { if ( primes [ i ]) { ++ cnt ; for ( int j = i + i ; j <= n ; j += i ) { primes [ j ] = false ; } } } return cnt ; } }using ll = long long ; const int MOD = 1e9 + 7 ; class Solution { public: int numPrimeArrangements ( int n ) { int cnt = count ( n ); ll ans = f ( cnt ) * f ( n - cnt ); return ( int ) ( ans % MOD ); } ll f ( int n ) { ll ans = 1 ; for ( int i = 2 ; i <= n ; ++ i ) ans = ( ans * i ) % MOD ; return ans ; } int count ( int n ) { vector < bool > primes ( n + 1 , true ); int cnt = 0 ; for ( int i = 2 ; i <= n ; ++ i ) { if ( primes [ i ]) { ++ cnt ; for ( int j = i + i ; j <= n ; j += i ) primes [ j ] = false ; } } return cnt ; } };class Solution : def numPrimeArrangements ( self , n : int ) -> int : def count ( n ): cnt = 0 primes = [ True ] * ( n + 1 ) for i in range ( 2 , n + 1 ): if primes [ i ]: cnt += 1 for j in range ( i + i , n + 1 , i ): primes [ j ] = False return cnt cnt = count ( n ) ans = factorial ( cnt ) * factorial ( n - cnt ) return ans % ( 10 ** 9 + 7 )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.