Leetcode - 1175. Prime Arrangements ( Tutorial + Solution in C )

=>Try Yourself First. For help Scroll Down.

Problem Link: https://leetcode.com/problems/prime-arrangements/

Problem Clearance: You will be given a number N. This problem said to figure out the count of permutations of numbers between 1 to N where the prime numbers of that range remain in prime positions. So, for example, you are given N as 5, you have to find out the number of permutations of 1, 2, 3, 4, 5 in such a way the prime numbers 2, 3, and 5 located at any of the prime'th position that is at any of the 2nd, 3rd, and 5th positions. So, now if you consider the permutation 1, 5, 3, 4, 2 then it is OK. But if you consider the permutation 2, 3, 1, 5, 4 then it will not OK as the prime number 2 is at 1st position.  As the answer could be very big you have to return the answer modulo 1000000007. 

So, if you receive an answer as 1000000011 you have to return 1000000011%1000000007 which is 4.

Required Knowledge: Prime Number.

Tutorial: The first part is to figure out the number of primes within 1 to N. According to the definition of prime number we know that, any number more than 1 can be considered as a prime number if it is divisible only by 1 and N itself. For example, 5 is a prime number and 8, is not. 

So as the definition implies we can count the number of primes between 1 to N. We will run a loop from 1 to N and for X, try to divide the number by any numbers inclined between 2 to X-1. If X is divisible by any number inclusive 2 and X-1 then X is not a prime number otherwise, it is a prime number. You can speed up the prime checking process but it is not that required as N is as low as 100.

Now, for the second part, we have to find out the permutation of numbers among 1 to N maintaining mentioned condition. For example, you are given N = 5. So you have 5 numbers, that is, 1,2 3, 4, 5. In the series of numbers, you can see there are 3 primes. Those are 2, 3, 5. The number of prime positions is also 3. For the 2nd position, we can place a number among 2, 3, 5 in 3 ways. Now one of the three numbers (2, 3, 5) is placed at 2nd position. 

Similarly, for the 3rd position, we can place any of the left two numbers in 2 way. We can place the remaining last number at the 5th position in 1 way. So, in total, we can place 3 prime in 3 prime positions in 3x2x1 = 6 ways. 

Similarly, if we calculate for the non-prime numbers, we will see we can place 2 non-prime numbers into two non-prime positions in 2x1 ways. So, in general, for N numbers they can be rearranged in 1x2x3x......xN = N! ways. 

Now, if we multiply both the arrangements for prime numbers with prime positions and the arrangements non-prime numbers with non-prime positions we will have the final answer. Return the result modulo 1000000007.

Tip: While doing factorial do the modulo calculation parallelly. As the factorial is nothing but the multiplication of numbers, it will propagate the modulated result throughout the calculation and you will have the exact result. If you do the modulo at the end of the calculation you will not get the exact answer as the number does not fit even in long long int data type. 

Hopefully, you solved it by now. You can see the code if you need to.

Code:

int numPrimeArrangements(int n) {
        long long primecount = 0;
        for(int i=2; i<=n; i++){
            for(int j=2; j<i; j++){
                if(i%j == 0) goto label;
            }
            primecount++;
            label:;
        }
        long long ans = 1;
        for(int i=1; i<=primecount; i++){
            ans = (ans * i)%1000000007;
        }
        for(int i=1; i<=(n-primecount); i++){
            ans = (ans * i)%1000000007;
        }
        return ans;
    }

=> Leave a comment for any kinds of Hugs and/or Bugs. Thank you.