Last Updated: 15 Apr, 2021

Prime Permutations

Moderate

Asked in company

Solve now

Problem statement

You are given an integer, ‘N’. Your task is to determine the total number of different permutations of the numbers from 1 to ‘N’, such that in every such permutation, all prime numbers within the range, 1 to ‘N’ are present at prime indices(1-indexed), and composite numbers at composite indices.

Note:

1. The permutation [1,4,3,2] is not a valid permutation because 2 is a prime number and thus it should be placed at a prime index but in this permutation, it is placed at index 4(1-indexed). Also, at index 2, a prime number should have been placed as 2 is a prime number but here, 4 is placed which is not a prime number. So, this is an invalid permutation.

2. The permutation [1,3,2,4] is a valid permutation because 2 and 3 are prime numbers, so index 2 and index 3 are prime indices. In this permutation, prime numbers are placed at prime indices only and composite numbers are placed at composite indices so this is a valid permutation.

Input Format:

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains a single integer, ‘N’.

Output Format:

For each test case, return a single integer, denoting the total number of required permutations. Since, the answer may be very large, print the answer modulo 10^9 + 7.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N < 100

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

The approach is to find out the total number of prime numbers in the range, 1 to ‘N’. Let this number be ‘X’. So, the total number of prime indices will also be ‘X’ and the total number of different ways in which the prime numbers can be placed at prime indices will be ‘X!’. The total number of composite numbers will be ‘N-X’. So, the total number of different ways in which the composite numbers can be placed at prime indices will be ‘(N-X)!’.

Steps:

Initialize a variable, say 'PRIME_COUNT'=0. This will store the total count of prime numbers in the given range.
Now, run a loop from 'NUM'=1 to 'NUM'<= ‘N’, and do:
1. If 'NUM' is a prime number, increase the value of 'PRIME_COUNT' by 1. Formally, if 'IS_PRIME'('NUM' == true), 'PRIME_COUNT'++.
Initialize a variable, say ‘MOD’, to the value 10^9 + 7.
Now, initialize a variable, say 'PERMUTATION_COUNT' = 1. This will store the total number of required permutations.
Now, run a loop from ‘i’ = 2 to ‘i’ <= 'PRIME_COUNT', and do:
1. 'PERMUTATION_COUNT' *= ‘i’. This is because we want to take the factorial of the value stored in 'PRIME_COUNT' or we can say we are arranging prime number on prime indices
2. After multiplying, always take modulo of the resultant value to avoid overflow. So, 'PERMUTATION_COUNT' %= ‘MOD’.
Now, run a loop from ‘i’ = 2 to ‘i’ <= (‘N’ - 'PRIME_COUNT'), and do:
1. 'PERMUTATION_COUNT' *= ‘i’. This is because we want to take the factorial of the value stored in (‘N’ - 'PRIME_COUNT') and here this value is count of non prime numbers.
2. After multiplying, always take modulo of the resultant value to avoid overflow. So, 'PERMUTATION_COUNT' %= ‘MOD’.
Finally, return the value of 'PERMUTATION_COUNT' .

Solve now

02 Approach

Approach:

The approach is to use the Sieve of Eratosthenes to find the count of prime numbers in the range, 1 to ‘N’. The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers smaller than ‘N’. We can learn more about Sieve of Eratosthenes here. The rest of the procedure to find the total number of different arrangements using the value of this count remains the same.

Steps:

Define a variable, say 'PRIME_COUNT', to store the result of sieve(n). The sieve will return the count of prime numbers within the range, 1 to ‘N’.
Initialize a variable, say 'MOD', to the value 10^9 + 7.
Now, initialize a variable, say 'PERMUTATION_COUNT' = 1. This will store the total number of required permutations.
Now, run a loop from i=2 to i<='PRIME_COUNT', and do:
1. 'PERMUTATION_COUNT' *= i. This is because we want to take the factorial of the value stored in 'PRIME_COUNT' or we can say we are arranging prime number on prime indices
2. After multiplying, always take modulo of the resultant value to avoid overflow. So, 'PERMUTATION_COUNT' %= 'MOD'.
Now, run a loop from i=2 to i <= (N - 'PRIME_COUNT'), and do:
1. 'PERMUTATION_COUNT' *= i. This is because we want to take the factorial of the value stored in (N - 'PRIME_COUNT') and here this value is count of non prime numbers.
2. After multiplying, always take modulo of the resultant value to avoid overflow. So, 'PERMUTATION_COUNT' %= 'MOD'.
Finally, return the value of 'PERMUTATION_COUNT' .

Int sieve(n) {

Define a boolean vector, say 'PRIME', of size n+1, and initialize all elements of this vector to true.
Initialize a variable, say 'COUNT' = 0.
Run a loop from num=2 to num*num<=n, and do:
1. If 'PRIME'[num] = true, do:
  1. Run another loop from i=num*num to i<=n, with an increment of a value equal to num, and make 'PRIME'[i] = false.
Run a loop from num=2 to num<=n, and do:
1. If 'PRIME'[num] = true, increment the value of 'COUNT' by 1.
Return the value of 'COUNT'.

Solve now