1175. Prime Arrangements

Problem Description

The problem is to find out how many different permutations of the numbers 1 to n can be constructed in such a way that all prime numbers are at prime indices, with indices considered to be 1-indexed (meaning they start from 1, not 0). Note that prime numbers are integers greater than 1 that have no divisors other than 1 and themselves.

It is important to understand that indices in a list and the actual numbers placed at those indices can be prime. Therefore, we need to consider two separate conditions for the permutation to meet the prime placement criteria: (1) The numbers themselves must be prime, and (2) Their positions in the permutation must also be prime index locations.

Given a number n, there will be a specific count of prime numbers within the range from 1 to n, and those prime numbers must be arranged in the prime indices. All the non-prime numbers, therefore, will go into the remaining positions.

Since the answer could potentially be a very large number, the problem asks us to return the result modulo 10^9 + 7, a common technique in algorithms to avoid integer overflow and to keep the numbers within a manageable range.

Intuition

The solution is based on combinatorics. Specifically, we can break down the problem into two separate tasks:

Counting the prime numbers from 1 to n. This tells us how many numbers need to be placed in prime index positions.
Calculating permutations of the prime numbers in the prime indices and the permutations of the non-prime numbers in the non-prime indices.

The Sieve of Eratosthenes algorithm, which is an efficient way to find all primes smaller than a given number, is a good approach to get the count of prime numbers. With this algorithm, we iterate over each number from 2 to n and mark multiples of each number (which cannot be prime) as non-prime. The numbers that remain unmarked at the end of this process are the prime numbers.

Once we count the number of primes within the range of 1 to n (let's say there are cnt primes), we then must calculate the total number of permutations of these cnt prime numbers, which is simply the factorial of cnt (factorial(cnt)).

Simultaneously, we must also calculate the permutations for the remaining n - cnt non-prime numbers, which can be arranged in any order in the remaining positions. The total permutations for these non-prime numbers are factorial(n - cnt).

The total number of prime arrangements is then the product of these two permutations: factorial(cnt) for the prime numbers and factorial(n - cnt) for the non-prime numbers.

The final step is to return this product modulo 10^9 + 7 to ensure the output fits within the expected range of values as required by the problem.

The solution code encloses the prime-counting logic within a function count, then calculates the factorials, multiplies them, and applies the modulo operation to return the answer.

Learn more about Math patterns.

Solution Approach

The implementation of the solution can be broken down into two main parts: counting prime numbers and computing factorials for the permutations.

Counting Prime Numbers using Sieve of Eratosthenes:
- The count function initiates a list primes of boolean values, initially set to True, representing the numbers from 0 to n. The boolean values will represent if a number is prime (True) or not (False).
- It then iterates over the list starting from the first prime number 2. For each number i, if i is marked as True (indicating it is still considered prime), we:
  - Increment the cnt which counts the number of primes.
  - Proceed to mark all multiples of i as False since they are not primes.
- After the loop completes, cnt holds the number of prime numbers between 1 and n.
Calculating Factorials:
- The number of permissible arrangements of prime numbers is calculated by taking the factorial of the count of prime numbers (factorial(cnt)).
- Similarly, for non-prime numbers, we use the factorial of the difference between the total count n and the count of prime numbers (factorial(n - cnt)).
Calculating the Answer:
- The answer to how many unique permutations of numbers are available such that primes are at prime indices is given by the product of these two factorials: factorial(cnt) * factorial(n - cnt).
- Since the product of these factorials can be very large, the final answer is taken modulo 10^9 + 7 to fit within the bounds specified by the problem and to avoid integer overflow.

Throughout the implementation, we see the use of basic data structures like lists (primes list for the sieve algorithm) and the use of the range function to traverse numbers and multiples. Due to Python's built-in modulo operation and factorial computation, no additional custom data structures or algorithms are required for computing factorials and their modulo.

In programming terms, this implementation leverages memoization implicitly by pre-computing the factorials of the numbers from 1 to n only once, thereby avoiding redundant calculations. This approach, combined with the efficiency of the Sieve of Eratosthenes, ensures that the algorithm runs in a relatively fast time frame appropriate for the size of input n.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let us illustrate the solution approach by walking through a small example. Consider the number n = 6. We want to find out how many permutations of the numbers 1 to 6 can be formed where prime numbers occupy prime indices (1-indexed).

Firstly, we need to identify the prime numbers from 1 to 6 and also the prime indices. The prime numbers will be 2, 3, and 5, and the prime indices are 2, 3, and 5 since 1 is not considered prime.

Now, apply Step 1: Counting Prime Numbers using the Sieve of Eratosthenes:

Initialize the primes list to track prime numbers up to n (ignoring 0 and 1). This looks like [True, True, True, True, True, True].
Starting from 2, mark non-prime multiples as False. The updated primes list becomes [True, True, True, True, False, True].
Count the number of True values excluding the first position which corresponds to 1. We have three primes 2, 3, 5 (which is cnt = 3).

Next, for Step 2: Calculating Factorials:

Calculate the factorial of the count of prime numbers (which is 3): factorial(3) = 3! = 6 to account for permutations among prime numbers.
Also calculate the factorial of non-prime numbers (n - cnt): factorial(6 - 3) = factorial(3) = 3! = 6.

Finally, in Step 3: Calculating the Answer:

Multiply the results of these factorials to find the total permutations: 6 * 6 = 36.
Take the result modulo 10^9 + 7 gives 36 mod (10^9 + 7) = 36.

So, for n = 6, there are 36 permutations where prime numbers occupy the prime indices.

Solution Implementation

1class Solution:
2    def numPrimeArrangements(self, n: int) -> int:
3        from math import factorial
4      
5        def count_primes(n: int) -> int:
6            """
7            Count the number of prime numbers less than or equal to n using the Sieve of Eratosthenes algorithm.
8            """
9            count = 0
10            is_prime = [True] * (n + 1)  # Initialize a list to track prime numbers
11
12            for i in range(2, n + 1):
13                if is_prime[i]:  # If i is a prime number
14                    count += 1
15                    for j in range(i * 2, n + 1, i):
16                        is_prime[j] = False  # Mark multiples of i as not prime
17            return count
18
19        prime_count = count_primes(n)
20      
21        # Calculate the number of arrangements as the factorial of the prime count,
22        # multiplied by the factorial of the count of non-prime numbers
23        arrangements = factorial(prime_count) * factorial(n - prime_count)
24      
25        # Return the number of arrangements modulo (10**9 + 7)
26        return arrangements % (10**9 + 7)
27

1class Solution {
2    private static final int MOD = (int) 1e9 + 7; // Constant for the modulo operation
3
4    // Counts the number of prime arrangements possible up to n
5    public int numPrimeArrangements(int n) {
6        int primeCount = countPrimes(n); // Counts the number of prime numbers up to n
7        long arrangements = factorial(primeCount) * factorial(n - primeCount);
8        // Computes the arrangements as prime! * (n - prime)!
9        return (int) (arrangements % MOD); // Returns the result modulo MOD
10    }
11
12    // Calculates the factorial of a number using the modulo operation
13    private long factorial(int n) {
14        long result = 1;
15        for (int i = 2; i <= n; ++i) {
16            result = (result * i) % MOD; // Calculates factorial with modulo at each step
17        }
18        return result;
19    }
20
21    // Counts the number of prime numbers up to n
22    private int countPrimes(int n) {
23        int count = 0; // Initialize count of primes to 0
24        boolean[] isPrime = new boolean[n + 1]; // Create an array to mark non-prime numbers
25        Arrays.fill(isPrime, true); // Assume all numbers are prime initially
26        for (int i = 2; i <= n; ++i) {
27            if (isPrime[i]) { // Check if the number is marked as a prime
28                ++count; // Increment the count of prime numbers
29                // Mark all multiples of i as non-prime
30                for (int j = i + i; j <= n; j += i) {
31                    isPrime[j] = false;
32                }
33            }
34        }
35        return count; // Return the count of prime numbers
36    }
37}
38

1using ll = long long; // Alias for long long type
2const int MOD = 1e9 + 7; // Constants should be in uppercase
3
4// Solution class containing methods for prime arrangements calculation
5class Solution {
6public:
7    // Calculates the number of prime arrangements for a given number n
8    int numPrimeArrangements(int n) {
9        int primeCount = countPrimes(n); // Count the number of primes up to n
10        // Calculate the factorial of prime count and non-prime count respectively,
11        // then multiply them together modulo MOD
12        ll arrangements = factorial(primeCount) * factorial(n - primeCount) % MOD;
13        return static_cast<int>(arrangements);
14    }
15
16    // Function to calculate factorial of a number n modulo MOD
17    ll factorial(int n) {
18        ll result = 1;
19        for (int i = 2; i <= n; ++i) {
20            result = (result * i) % MOD;
21        }
22        return result;
23    }
24
25    // Function to count the number of prime numbers up to n
26    int countPrimes(int n) {
27        vector<bool> isPrime(n + 1, true); // Create a sieve initialized to true
28        int primeCount = 0;
29        for (int i = 2; i <= n; ++i) {
30            if (isPrime[i]) {
31                ++primeCount; // Increment count if i is a prime
32                // Mark all multiples of i as non-prime
33                for (int j = i * 2; j <= n; j += i) {
34                    isPrime[j] = false;
35                }
36            }
37        }
38        return primeCount;
39    }
40};
41

1// Define type alias for bigint
2type BigIntAlias = bigint;
3
4// Constant for modular arithmetic
5const MOD: BigIntAlias = BigInt(1e9 + 7);
6
7/**
8 * Calculates the factorial of a number `n` modulo `MOD`.
9 * @param n The number to calculate the factorial of.
10 * @returns The factorial of `n` modulo `MOD`.
11 */
12function factorial(n: number): BigIntAlias {
13    let result: BigIntAlias = BigInt(1);
14    for (let i = 2; i <= n; ++i) {
15        result = (result * BigInt(i)) % MOD;
16    }
17    return result;
18}
19
20/**
21 * Counts the number of prime numbers up to `n`.
22 * @param n The number up to which to count primes.
23 * @returns The count of prime numbers up to `n`.
24 */
25function countPrimes(n: number): number {
26    const isPrime: boolean[] = new Array<boolean>(n + 1).fill(true);
27    let primeCount: number = 0;
28    for (let i = 2; i <= n; ++i) {
29        if (isPrime[i]) {
30            primeCount++;
31            for (let j = i * 2; j <= n; j += i) {
32                isPrime[j] = false;
33            }
34        }
35    }
36    return primeCount;
37}
38
39/**
40 * Calculates the number of prime arrangements for a given number `n`.
41 * @param n The number to calculate prime arrangements for.
42 * @returns The number of prime arrangements for `n`.
43 */
44function numPrimeArrangements(n: number): number {
45    const primeCount: number = countPrimes(n);
46    const arrangements: BigIntAlias = (factorial(primeCount) * factorial(n - primeCount)) % MOD;
47    return Number(arrangements);
48}
49

Time and Space Complexity

Time Complexity

The time complexity of the count function is O(n * log(log(n))). This is because the sieve of Eratosthenes, which is used to find all prime numbers up to n, has a time complexity of O(n * log(log(n))).

The factorial function (which is not shown here, but its complexity can be derived from typical implementations) typically has a time complexity of O(n). Given that the maximum value for factorial calculation is n, two such calculations are performed - one for the prime count cnt and one for the non-prime count n - cnt.

Therefore, the overall time complexity of the code is dominated by the sieve in the count function, which gives us the total time complexity: O(n * log(log(n)) + n + n), simplifying to O(n * log(log(n))).

Space Complexity

For space complexity, the count function allocates an array primes of size n + 1, which leads to O(n) space complexity. The space requirement for the calculation of the factorial depends on the implementation, but typically, it can be calculated in O(1) space.

Therefore, the overall space complexity of the code is O(n) for the sieve of Eratosthenes array storage.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know