Prime Arrangements

EASY

Description

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

Checkout 3 different approaches to solve Prime Arrangements. Click on different approaches to view the approach and algorithm in detail.

Optimized Primality Test

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 primeCount to 0.
Iterate from i = 1 to n.
For each i, check if it's a prime number using an optimized primality test (checking divisibility from 2 to sqrt(i)).
If i is prime, increment primeCount.
Calculate nonPrimeCount = n - primeCount.
Calculate factorial(primeCount) and factorial(nonPrimeCount) modulo 10^9 + 7.
Return the product of the two factorials modulo 10^9 + 7.

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 n using the optimized isPrime function.
Calculate primeCount and nonPrimeCount.
Compute (primeCount!) * ((n - primeCount)!) modulo 10^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 Analysis

Time Complexity: O(n * sqrt(n)). We iterate `n` times, and each primality test takes up to O(sqrt(n)) time.Space Complexity: O(1). No extra space proportional to `n` is used.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Prime Arrangements. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Prime Arrangements

Patterns:

Math