[Solved] Langford Pairing Contest Problem

Langford Pairing: You are given a positive integer N. Return a list of integers of size 2N containing all the integers from 1 to N (both inclusive) twice arranged according to Langford pairing. If no such pairing exists return -1 is the only list element.

Note:

There may be more than one Langford pair possible, you need to return anyone permutation.

For Example:

For N = 4, one possible Langford pairing will be:-

Langford Pairing Contest Problem

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and only line of each test case or query contains the integer N. 

Output Format:

The only line of output contains “Valid” if the answer is correct and “Invalid” if it’s not, without quotes. 

Note:

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

Constraints:

1 <= T <= 5
0 <= N <= 32

Time Limit: 1 sec

Sample Input 1:

2
4
5

Sample Output 1:

4 1 3 1 2 4 3 2 
-1

Explanation For Sample Input 1:

For the first test case:

 For the second test case: No Langford pairing is possible, hence print -1. 

Sample Input 2:

1
15

Sample Output 2:

15 13 14 8 5 12 7 11 4 10 5 9 8 4 7 13 15 14 12 11 10 9 6 3 1 2 1 3 2 6

Solution

/*
    Time complexity: O(N ^ N)
    Space complexity: O(N) 
    
    Where N is the input integer.
*/

import java.util.Arrays;
import java.util.HashMap;

public class Solution 
{

    public static int[] findLangford(int n) 
    {
        
        if(n % 4 == 1 || n % 4 == 2) 
        {
            return new int[] {-1};
        }
        
        int[] ans = new int[2 * n];
        
        findLangfordHelper(ans, n);
        
        return ans;
        
    } 

    public static boolean findLangfordHelper(int[] ans, int n) 
    {

        if(n == 0) 
        {
            return true;
        }
        
        for(int i = 0; i < ans.length - n - 1; i++) 
        {
            
            // If empty slot
            if(ans[i] == 0 && ans[i + n + 1] == 0) 
            {
                
                // Fill slot
                ans[i] = n;
                ans[i + n + 1] = n;
                
                // Recursively call to fill remaining elements.
                if(findLangfordHelper(ans, n - 1)) 
                {
                    return true;
                }
                
                // Undo
                ans[i] = 0;
                ans[i + n + 1] = 0;

            }
        } 

        return false;

    }


}

/*
    Time complexity: O(N ^ N)
    Space complexity: O(N) 
    
    Where N is the input integer.
*/

bool findLangfordHelper(vector<int> &ans, int n) 
{

    if(n == 0) 
	{
        return true;
    }
    
    for(int i = 0; i < ans.size() - n - 1; i++)
	{
        
        // If empty slot
        if(ans[i] == 0 && ans[i + n + 1] == 0) 
		{
            
            // Fill slot
            ans[i] = n;
            ans[i + n + 1] = n;
            
            // Recursively call to fill remaining elements.
            if(findLangfordHelper(ans, n - 1)) 
			{
                return true;
            }
            
            // Undo
            ans[i] = 0;
            ans[i + n + 1] = 0;

        }
    } 

    return false;

}

vector<int> findLangford(int n) 
{
    
    if(n % 4 == 1 || n % 4 == 2) 
	{
        vector<int> ans(1, -1);
        return ans;
    }
    
    vector<int> ans(2 * n, 0);
    
    findLangfordHelper(ans, n);
    
    return ans;
    
} 

'''
    Time complexity: O(N ^ N)
    Space complexity: O(N) 
    
    Where N is the input integer.
'''

def findLangfordHelper(ans, n):

    if(n == 0): 
        return True
    
    for i in range(len(ans)-n-1):
        
        # If empty slot
        if (ans[i] == 0 and ans[i + n + 1] == 0):
            
            # Fill slot
            ans[i] = n
            ans[i + n + 1] = n

            # Recursively call to fill remaining elements.
            if (findLangfordHelper(ans, n - 1)):
                return True
            
            # Undo
            ans[i] = 0
            ans[i + n + 1] = 0
 
    return False

def findLangford(n):
    
    if(n % 4 == 1 or n % 4 == 2):
        ans=[-1]
        return ans
    ans=[0]*(2 * n)
    findLangfordHelper(ans, n)
    return ans 

Happy Learning – If you require any further information, feel free to contact me.