1.
Introduction
2.
Solution Approach
2.1.
Idea
2.2.
Algorithm
2.3.
C++ Code implementation
2.4.
Output
2.5.
Complexity Analysis
2.5.1.
Time complexity: O(N!)
2.5.2.
Space complexity: O(1)
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024

# Count the permutations of first N positive integers such that the sum of any two consecutive numbers is prime

Ayush Prakash
1 upvote

## Introduction

Let us discuss the problem statement. We are given an integer N. We need to count the permutations of first N positive integers such that the sum of any two consecutive numbers in the permutation is a prime number. Also, the sum of the first and the last number in the permutation should be prime. All cyclic permutations are counted as one.

Input

N = 4

Output

2

Explanation

The two valid permutations following the given constraints are: {1, 4, 3, 2} and {1, 2, 3, 4}. Note that the sum of any two consecutive numbers is a prime. Also, the first and last number adds up to a prime number.

{1, 2, 3, 4}., {4, 1, 2, 3}, {3, 4, 1, 2} etc… are all counted as one because they are cyclic permutations of one another.  Hence, the count the permutations of first N positive integers following all the constraints is 2.

Input

N = 5

Output

0

Explanation:

There are no such permutations that follow the given constraints.

Input

8

Output

4

Explanation

The permutations following the given constraints are:

1 2 3 8 5 6 7 4

1 2 5 8 3 4 7 6

1 4 7 6 5 8 3 2

1 6 7 4 3 8 5 2

Hence, the count the permutations of first N positive integers, where N = 8, following all the constraints is 4.

## Solution Approach

### Idea

We will use recursion and backtracking to solve the problem of Count the permutations of first N positive integers. We will build every possible permutation recursively. While building a permutation, we ensure that all the constraints provided are followed. Since all the cyclic permutations are counted as one, we need not build all of them. To achieve this, we fix the first number in the permutation as one (it could be any number in the range [1, N], but it should be the same for all permutations).

### Algorithm

1. We declare two arrays, ‘isPrime[]’ and ‘taken[]’. ‘isPrime[]’ is a boolean array that gives information about whether a number is prime or not. isPrime[i] = true, means i is a prime number. taken[] is also a boolean array. It provides information about whether a number is used in the permutation or not. taken[i] = true, means is part of the current permutation that is being built by the algorithm.
2. We define a wrapper function ‘countPerm(int N)’. The function definition goes like this:
1. We set the size of isPrime[] to 2N because we are working with numbers in the range [1, N], the maximum sum of any two consecutive numbers in a permutation is (N) + (N - 1) = 2N - 1. Therefore the size of the isPrime[] array is 2N.
2. Call the simpleSieve() method. ‘simpleSieve()’ updates isPrime[i] (0 <= i < 2N) as true/false based on the fact that i is prime or not.
3. Reset the size of ‘taken[]’ to ‘N+1’.
4. Declare an empty array ‘perm[]’ that holds the current permutation. Push 1 into perm[] and mark taken[1] = true.
5. Set ANS = 0. This stores the answer.
6. Call ‘countPermHelper(N, ANS, perm[])’. This function executes the logic(recursion + backtracking).
7. PrintANS’.
3. We define ‘countPermHelper(N, ANS, perm[])’ as:
1. Initialize IDX = size of perm[]. ‘IDX’ is the index where we want to place a number.
2. Check for the base case. If IDX = N, increment ‘ANS’ as ANS = ANS + 1 and return. When IDX = N, it means that no number in [1, N] is left to be put in the permutation.
3. Run a loop from i = 2 to N, push ‘i’ into the perm[] if it is not used in the permutation i.e taken[i] = false and i + immediate previous number in the permutation is a prime number i.e. isPrime[i + perm[IDX - 1]] = true. There is one edge case to handle. When IDX = N - 1, when ‘IDX’ points to the last space in the perm[] array, check if i + 1 is prime or not. Because one of the constraints is the sum of the first and the last number in the permutation must also be a prime.
4. Make a recursive call to ‘countPermHelper(N, ANS, perm[])’ to build a valid permutation.

Note: In the implementation, we have used perm.back() which is equivalent to perm[IDX-1].

### Complexity Analysis

#### Time complexity: O(N!)

Time Complexity of Count the permutations of first N positive integers in O(N!). As, we are essentially trying to form every permutation and check if it follows the given constraints. From basic permutations and combinations, we know that the number of ways to arrange N objects is N!. Technically, it is (N - 1) for the above solution since we are fixing the first number to 1. Therefore the overall time complexity is O(N!).

#### Space complexity: O(1)

Space Complexity for Count the permutations of first N positive integers is O(1). If we ignore the space used by the recursion call stack, we are not using any auxiliary space. Therefore, the space complexity is O(1).

Also see, Euclid GCD Algorithm

## FAQs

1. What are cyclic permutations? Explain.
Two permutations are cyclic if, when one of the permutations is shifted by some offset, we obtain the other permutation. For example, {1,2,3,4} and {3,4,1,2} are cyclic permutations because when you right shift {1, 2, 3, 4} by 2 (offset) and you will get {3, 4, 1, 2}.

2. What is the core logic behind the simpleSieve algorithm?
The simpleSieve algorithm is used to generate prime numbers <= N (some number). In this algorithm, all multiples of all prime numbers in [1, N] are cancelled. This is done in a very efficient manner. In the end, we are left with the information that which numbers are prime and which are not.

## Key Takeaways

In this blog, we solved a really interesting problem: Count the permutations of first N positive integers such that the sum of any two consecutive numbers is prime using recursion and backtracking. We also analyzed the space and time complexity of the approach discussed.

Recursion is a very important concept in programming, and it is used in a variety of problems. It is used in trees, graphs, dynamic programming, backtracking etc. If you are struggling with recursion, follow this amazing course.

Check out this problem - Pair Sum In Array.