Prime Permutations

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
23 upvotes
Asked in company
Ola

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
3
Sample Output 1:
2
Explanation for sample input 1:
There are only two different permutations of the numbers from 1 to 3, in which the prime numbers are present at prime indices. These two permutations are:
1, 2, 3
1, 3, 2

There are only two prime numbers in the range of 1 to 3. These two numbers are 2 and 3. So the prime indices will be 2 and 3(1-indexed). We can observe in all the above-mentioned permutations, that at index 2 and 3, there are only prime numbers. There does not exist any other permutation, where all this condition is satisfied. Hence, we print 2 as our answer.
Sample Input 2:
1
4
Sample Output 2:
4
Explanation for sample input 2:
There are only four different permutations of the numbers from 1 to 4, in which the prime numbers are present at prime indices. These four permutations are:
1, 2, 3, 4
1, 3, 2, 4
4, 2, 3, 1
4, 3, 2, 1

There are only two prime numbers in the range of 1 to 4. These two numbers are 2 and 3. So the prime indices will be 2 and 3(1-indexed). We can observe in all the above-mentioned permutations, that at index 2 and 3, there are only prime numbers. There does not exist any other permutation, where all this condition is satisfied. Hence, we print 4 as our answer.
Hint

Count all prime numbers in the given range

Approaches (2)
Finding all prime numbers

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:

  1. Initialize a variable, say 'PRIME_COUNT'=0. This will store the total count of prime numbers in the given range.
  2. 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'++.
  3. Initialize a variable, say ‘MOD’, to the value 10^9 + 7.
  4. Now, initialize a variable, say 'PERMUTATION_COUNT' = 1. This will store the total number of required permutations.
  5. 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’.
  6. 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’.
  7. Finally, return the value of 'PERMUTATION_COUNT' .
Time Complexity

O(N * sqrt(N) ), where 'N' is the upper bound of the range in which numbers are to be considered.

 

We are going through all the numbers in the range 1 to N, one by one, and checking if the number is prime or not. This checking of a single number takes O(sqrt(N)) time. So, the overall time complexity will become O(N * sqrt(N) ).

Space Complexity

O(1).

 

We are not using any extra space.

Code Solution
(100% EXP penalty)
Prime Permutations
Full screen
Console