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.
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 ; } }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.