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 listprimes
of boolean values, initially set toTrue
, representing the numbers from 0 ton
. 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
, ifi
is marked asTrue
(indicating it is still considered prime), we:- Increment the
cnt
which counts the number of primes. - Proceed to mark all multiples of
i
asFalse
since they are not primes.
- Increment the
- After the loop completes,
cnt
holds the number of prime numbers between 1 andn
.
- The
-
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)
).
- The number of permissible arrangements of prime numbers is calculated by taking the factorial of the count of prime numbers (
-
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.
- 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:
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 EvaluatorExample 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 ton
(ignoring 0 and 1). This looks like[True, True, True, True, True, True]
. - Starting from
2
, mark non-prime multiples asFalse
. The updatedprimes
list becomes[True, True, True, True, False, True]
. - Count the number of
True
values excluding the first position which corresponds to1
. We have three primes2, 3, 5
(which iscnt
= 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
gives36 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.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
14
1public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
1function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!