Find Permutation

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in companies
Goldman SachsOlaFacebook

Problem statement

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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
1
3
Sample Output 1 :
-1
Valid
Explanation for Sample Input 1 :
In the first test case, No permutation is possible satisfying the given conditions as only [1, 1] is possible, and there are exactly 0 numbers between them.

In the second test case, Output is Valid as [3,1,2,1,3,2] is one of the possible permutations.  Here, the indices of ‘1’ are 1 and 3, and there is exactly 1 number between them, the indices of ‘2’ are 2 and 5, and there are exactly 2 numbers between them, the indices of ‘3’ are 0 and 4, and there are exactly 3 numbers between them.
Another possible array is [2, 3, 1, 2, 1, 3]. In this permutation, the indices of ‘1’ are 2 and 4 and there is exactly one number between them, the indices of ‘2’ are 0 and 3, and there are exactly two numbers between them, the indices of ‘3’ are 1 and 5, and there are exactly three numbers between them.
Sample Input 2 :
1   
4
Sample Output 2 :
Valid
Hint

Generate all the possible permutations and check if it is valid.

Approaches (2)
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:

  1. 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.
  2. 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.
  3. 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.
Time Complexity

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)! ) ).

Space Complexity

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).

Code Solution
(100% EXP penalty)
Find Permutation
Full screen
Console