Find Permutation
You are given an integer ‘N’. You need to find an array of size 2*N that satisfies the following two conditions.

1. All numbers from 1 to N should appear exactly twice in the array.

2. The distance between the second occurrence and the first occurrence of any number should exactly be equal to the value of that number.

The distance between two numbers at indices ‘i’ and ‘j’ is defined as (j-i-1) where i

Question

Find Permutation

You are given an integer ‘N’. You need to find an array of size 2*N that satisfies the following two conditions.

1. All numbers from 1 to N should appear exactly twice in the array.

2. The distance between the second occurrence and the first occurrence of any number should exactly be equal to the value of that number.

The distance between two numbers at indices ‘i’ and ‘j’ is defined as (j-i-1) where i < j.

If no such array exists, then you should return an empty array.

For example :

For N = 3 one valid array is [3,1,2,1,3,2].

Input Format :

The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first and the only line of each test case contains a single integer ‘N’.

Output Format :

The checker will print “Valid” if the returned permutation is valid and follows all the conditions, otherwise, it will print “Invalid”. If an empty array is returned, the checker will print -1.

Print the output of each test case in a new line.

Note :

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

Constraints :

1<= T <= 5
1 <= N <= 8

where ’T’ is the number of test cases and ‘N’  is the given integer.

Time Limit: 1 sec

Accepted Answer

Brute Force

The idea is to make an array with exactly two occurrences of each element from 1 to N. Then we will generate all possible permutations of this array and check if any permutation is valid or not.

The steps are as follows:

Let’s define a recursive function as generatePermutations(arr, answer, N, start, end), where arr is the array containing the permutation, answer is array that will store the final answer, ‘N’ is the given integer, ‘start’ is the starting index, and ‘end’ is the ending index. We will use this function to generate all possible permutations of the subarray of arr starting at index start and ending at index end.
Base condition: if ‘start’ is equal to ‘end’, then check if there are exactly k elements between both the occurrences of number ‘k’ for all valid ‘k’. (1<=k<=N). If it follows all the conditions, then make answer equal to the current array. Else ignore this array.
Iterate from i = start to end :
1. Swap the elements at index start, and i.
2. Call the recursive function again with left index as start+1, and right index as end i.e. generatePermutations(arr,start+1,end).
3. Swap back the elements at index start and i.

Space Complexity: O(n)Explanation:

O(N), where N is the given integer.

In the worst case, the recursion stack can grow up to a size of 2*N. Hence, the overall space complexity is O(N).

Time Complexity: OtherExplanation:

O( (N)*( (2*N)! ) ), where N is the given integer.

There are (2*N)! Permutations of the array and for each permutation, we need to check if it is valid or not, which will take O(N) time. Hence, the overall time complexity is O( (N)*( (2*N)! ) ).

Accepted Answer

Backtracking based Approach

This approach is similar to the previous approach but the idea is to carry on the recursion forward only if there are exactly k number of elements between both the occurrences of number ‘k’ (1<=k<=N). This way we can eliminate some function calls and reduce the time complexity.

Make an array of size 2*N initialized with 0 at each index. 0 will denote that a position is empty.
Let’s define a recursive function as generatePermutations(arr, answer, N, currElement), where arr is the array containing the elements of the permutation that we have generated so far, answer is an array that will store the final answer, ‘N’ is the given integer, currElement is the current element(starting from 1 and going till N as we proceed in the recursion).
Initially, the size of the vector answer is 0. Before proceeding with any step, we check whether the size of the vector answer is 0 or not.
1. If the size is not 0, it means we already got the answer, and there is no need to carry on the recursion. So, we immediately return from the function.
Base condition: if the current element is equal to N+1, it means all the elements are filled in their respective positions satisfying the given requirements, and this is one of the answers. Hence, we will make answer array equal to arr.
Iterate from i = 0 to 2*N-1:
1. If the element at the current position is 0 and the element at the current position + currElement+1 at position is also 0, that means both the positions can be filled with the current element.
2. Fill both the positions with the current element i.e do arr[i] = currElement and arr[i+currElement+1] = currElement.
3. Recursively call for the next element i.e generatePermutations(arr, answer, N, currElement+1).
4. Remove current element from both the filled positions (Backtracking).

Space Complexity: O(n)Explanation:

O(N), where N is the given integer.

In the worst case, the recursion stack can grow up to a size of N. Hence, the overall space complexity is O(N).

Time Complexity: O(n!)Explanation:

O(N!), where N is the given integer.

There are N! Possible permutations of numbers from 1 to N. In the worst case when there is no possible array that satisfies all the conditions, we will end up trying all the N! permutations. Hence, the overall time complexity is O(N!).

Java (SE 1.8)

/*

    Time Complexity: O(N!)

    Space Complexity: O(N)



    Where 'N' is the given integer

*/



import java.util.ArrayList;



public class Solution {

    static void generatePermutations(int[] arr, ArrayList answer, int N, int currElement) {

        // Check if we already have a answer

        if (answer.size() > 0) {

            return;

        }



        // Base Condition

        if (currElement > N) {



            for (int i = 0; i < 2 * N; i++) {

                answer.add(arr[i]);

            }



            return;

        }



        // Iterate through the array and find all valid positions

        for (int i = 0; i < 2 * N; i++) {



            int firstIndex = i, secondIndex = i + currElement + 1;



            // Checking if elements can be filled at both the valid positions

            if (secondIndex < 2 * N && arr[firstIndex] == 0 && arr[secondIndex] == 0) {

                arr[firstIndex] = currElement;

                arr[secondIndex] = currElement;



                // Recurse for the next element

                generatePermutations(arr, answer, N, currElement + 1);



                // Remove currElement element from both the filled positions (Backtrack).

                arr[firstIndex] = 0;

                arr[secondIndex] = 0;

            }

        }

    }



    public static ArrayList findPermutation(int n) {

        int[] arr = new int[2 * n];



        ArrayList answer = new ArrayList<>();



        generatePermutations(arr, answer, n, 1);



        return answer;



    }



}

C++ (g++ 5.4)

/*
    Time Complexity: O(N!)
    Space Complexity: O(N)

    Where 'N' is the given integer
*/

void generatePermutations(vector &arr, vector &answer, int N, int currElement)
{
    // Check if we already have a answer
    if (answer.size() > 0)
    {
        return;
    }

    // Base Condition
    if (currElement > N)
    {
        answer = arr;
        return;
    }

    // Iterate through the array and find all valid positions
    for (int i = 0; i < 2 * N; i++)
    {

        int firstIndex = i, secondIndex = i + currElement + 1;

        // Checking if elements can be filled at both the valid positions
        if (secondIndex < 2 * N && arr[firstIndex] == 0 && arr[secondIndex] == 0)
        {
            arr[firstIndex] = currElement;
            arr[secondIndex] = currElement;

            // Recurse for the next element
            generatePermutations(arr, answer, N, currElement + 1);

            // Remove currElement element from both the filled positions (Backtrack).
            arr[firstIndex] = 0;
            arr[secondIndex] = 0;
        }
    }
}
vector findPermutation(int N)
{
    vector arr(2 * N, 0);

    vector answer;

    generatePermutations(arr, answer, N, 1);
    
    return answer;
}

Python (3.5)

'''

    Time Complexity: O(N!)

    Space Complexity: O(N)



    where 'N' is the given integer

'''



def generatePermutations(arr, answer, N, currElement):



    # Check if we already have a answer

    if (len(answer) > 0):

        return

    

    # Base condition

    if (currElement > N):

        for i in arr:

            answer.append(i)

        return



    # Iterate through the array and find all valid positions

    for i in range(2 * N):

        firstIndex, secondIndex = i, i + currElement + 1



        if (secondIndex < 2 * N and arr[firstIndex] == 0 and arr[secondIndex] == 0):

            arr[firstIndex], arr[secondIndex] = currElement, currElement

            

            # Recurse for the next element

            generatePermutations(arr, answer, N, currElement + 1)

            

            # Remove currElement element from both the filled positions (Backtrack).

            arr[firstIndex], arr[secondIndex] = 0, 0





def findPermutation(N):

    arr = [0] * (2 * N)

    

    answer = []



    generatePermutations(arr, answer, N, 1)



    return answer