Generate a N length Permutation having equal sized LIS from both ends
Given an integer N, the task is to generate a permutation of elements in the range [1, N] in such order that the length of LIS from starting is equal to LIS from the end of the array. Print -1 if no such array exists.
Examples:
Input: N = 5
Output: [1, 3, 5, 4, 2]
Explanation:
LIS from left side: [1, 3, 5]
LIS from right side: [2, 4, 5]
Length of LIS from left and right side is same that is 3.Input: N = 7
Output: [1, 3, 4, 7, 6, 5, 2]
Explanation:
LIS from left side: [1, 3, 4, 7]
LIS from right side: [2, 5, 6, 7]
Length of LIS from left and right side is same that is 4.
Approach: Use the below observation to solve this problem:
- If N = 2, then such an array doesn’t exist.
- Else if N is odd,
- Then start by adding 1 at index 0 and adding 2 at index N-1.
- Now, add N at index N/2. After that, if N>3 then add remaining numbers 3, 4, 5, ... so on indices 1, 2, …, (N/2-1).
- Now add remaining numbers in decreasing order from index N/2+1 to N-2.
- If N is even,
- say 4 then it has only 1 possible solution: {2, 1, 4, 3}.
- After 4, suppose N = 6, then just add 6 at starting and 5 at ending to the previous answer for N = 4 which forms array = [6, 2, 1, 4, 3, 5].
- Similarly, for next even N just add N at 0th index and N-1 at last index..
Follow the steps mentioned below to solve the problem:
- If the size mentioned is 2, then return -1.
- Otherwise, add the elements as per the observation mentioned above.
- Return the formed list and print the list elements.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to create array having // same LIS from both sides vector< int > equalLIS( int N) { // If N = 2 we can't create array if (N == 2) { vector< int > al; al.push_back(-1); return al; } // If N is odd it is possible // to make an array else if (N % 2 != 0) { // Hash Map contains index // with its value map< int , int > lis; // indices 0, N/2, and N-1 lis.insert({ 0, 1 }); lis.insert({ N - 1, 2 }); int mid = N / 2; lis.insert({ mid, N }); if (N > 3) { // Adding numbers 3, 4, ... // and so on at index from // 1 to mid-1 respectively int val = 3; for ( int i = 1; i < mid; i++) { lis.insert({ i, val }); val++; } // Adding remaining integers // in decreasing order // from mid+1 to N-2 val = N - 1; for ( int i = mid + 1; i < N - 1; i++) { lis.insert({ i, val }); val--; } } // Creating Array List // which will use to form // required array vector< int > al; // Traversing from smallest key // to largest key in Hash Map // and adding its value in list for ( int i = 0; i < N; i++) { al.push_back(lis[i]); } // Returning formed array return al; } else { // Hash Map which contains // index with its value map< int , int > lis; // Adding value for N=4 in Hash Map lis.insert({ 0, 2 }); lis.insert({ 1, 1 }); lis.insert({ 2, 4 }); lis.insert({ 3, 3 }); int i = 3; int idx = 0; if (N >= 6) { i++; idx--; // Adding new N at starting index // and N-1 at last index int val = 5; while (val <= N) { lis.insert({ i, val }); lis.insert({ idx, val + 1 }); idx--; i++; val += 2; } } // Creating Array List // which will use to form // required array vector< int > al; // Traversing from minimum key // to maximum key add // adding its value in Array List for ( int j = idx + 1; j < i; j++) { al.push_back(lis[j]); } // Returning formed array return al; } } // Driver Code int main() { int N = 7; vector< int > lis = equalLIS(N); for ( auto x : lis) cout << x << " " ; return 0; } // This code is contributed by rakeshsahni |
Java
// Java program for the above approach import java.util.*; class GFG { // Driver Code public static void main(String[] args) { int N = 7 ; List<Integer> lis = equalLIS(N); for ( int x : lis) System.out.print(x + " " ); } // Function to create array having // same LIS from both sides public static List<Integer> equalLIS( int N) { // If N = 2 we can't create array if (N == 2 ) { List<Integer> al = new ArrayList<>(); al.add(- 1 ); return al; } // If N is odd it is possible // to make an array else if (N % 2 != 0 ) { // Hash Map contains index // with its value Map<Integer, Integer> lis = new HashMap<>(); // Adding 1, N, and 2 at // indices 0, N/2, and N-1 lis.put( 0 , 1 ); lis.put(N - 1 , 2 ); int mid = N / 2 ; lis.put(mid, N); if (N > 3 ) { // Adding numbers 3, 4, ... // and so on at index from // 1 to mid-1 respectively int val = 3 ; for ( int i = 1 ; i < mid; i++) { lis.put(i, val); val++; } // Adding remaining integers // in decreasing order // from mid+1 to N-2 val = N - 1 ; for ( int i = mid + 1 ; i < N - 1 ; i++) { lis.put(i, val); val--; } } // Creating Array List // which will use to form // required array List<Integer> al = new ArrayList<>(); // Traversing from smallest key // to largest key in Hash Map // and adding its value in list for ( int i = 0 ; i < N; i++) { al.add(lis.get(i)); } // Returning formed array return al; } else { // Hash Map which contains // index with its value Map<Integer, Integer> lis = new HashMap<>(); // Adding value for N=4 in Hash Map lis.put( 0 , 2 ); lis.put( 1 , 1 ); lis.put( 2 , 4 ); lis.put( 3 , 3 ); int i = 3 ; int idx = 0 ; if (N >= 6 ) { i++; idx--; // Adding new N at starting index // and N-1 at last index int val = 5 ; while (val <= N) { lis.put(i, val); lis.put(idx, val + 1 ); idx--; i++; val += 2 ; } } // Creating Array List // which will use to form // required array List<Integer> al = new ArrayList<>(); // Traversing from minimum key // to maximum key add // adding its value in Array List for ( int j = idx + 1 ; j < i; j++) { al.add(lis.get(j)); } // Returning formed array return al; } } } |
Python3
# Python3 program for the above approach # Function to create array having # same LIS from both sides def equalLIS(N): # If N = 2 we can't create array if (N = = 2 ): al = [] al.append( - 1 ) return al # If N is odd it is possible # to make an array elif (N % 2 ! = 0 ): # Hash Map(dictionary) contains index # with its value lis = {} # indices 0, N/2, and N-1 lis[ 0 ] = 1 lis[N - 1 ] = 2 mid = N / / 2 lis[mid] = N if (N > 3 ): # Adding numbers 3, 4, ... # and so on at index from # 1 to mid-1 respectively val = 3 for i in range ( 1 , mid): lis[i] = val val + = 1 # Adding remaining integers # in decreasing order # from mid+1 to N-2 val = N - 1 for i in range (mid + 1 , N - 1 ): lis[i] = val val - = 1 # Creating Array List # which will use to form # required array al = [] # Traversing from smallest key # to largest key in Hash Map # and adding its value in list for i in range (N): al.append(lis[i]) # Returning formed array return al else : # Hash Map which contains # index with its value lis = {} # Adding value for N=4 in Hash Map lis[ 0 ] = 2 lis[ 1 ] = 1 lis[ 2 ] = 4 lis[ 3 ] = 3 i = 3 idx = 0 if (N > = 6 ): i + = 1 idx - = 1 # Adding new N at starting index # and N-1 at last index val = 5 while (val < = N): lis[i] = val lis[idx] = val + 1 idx - = 1 i + = 1 val + = 2 # Creating Array List # which will use to form # required array al = [] # Traversing from minimum key # to maximum key add # adding its value in Array List for j in range (idx + 1 , i): al.append(lis[j]) # Returning formed array return al # Driver Code N = 7 lis = equalLIS(N) for x in lis: print (x, end = " " ) # This code is contributed by vikkycirus |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Driver Code public static void Main( string [] args) { int N = 7; List< int > lis = equalLIS(N); for ( int i = 0; i < lis.Count; i++) Console.Write(lis[i] + " " ); } // Function to create array having // same LIS from both sides public static List< int > equalLIS( int N) { // If N = 2 we can't create array if (N == 2) { List< int > al = new List< int >(); al.Add(-1); return al; } // If N is odd it is possible // to make an array else if (N % 2 != 0) { // Hash Map contains index // with its value Dictionary< int , int > lis = new Dictionary< int , int >(); // Adding 1, N, and 2 at // indices 0, N/2, and N-1 lis[0] = 1; lis[N - 1] = 2; int mid = N / 2; lis[mid] = N; if (N > 3) { // Adding numbers 3, 4, ... // and so on at index from // 1 to mid-1 respectively int val = 3; for ( int i = 1; i < mid; i++) { lis[i] = val; val++; } // Adding remaining integers // in decreasing order // from mid+1 to N-2 val = N - 1; for ( int i = mid + 1; i < N - 1; i++) { lis[i] = val; val--; } } // Creating Array List // which will use to form // required array List< int > al = new List< int >(); // Traversing from smallest key // to largest key in Hash Map // and adding its value in list for ( int i = 0; i < N; i++) { al.Add(lis[i]); } // Returning formed array return al; } else { // Hash Map which contains // index with its value Dictionary< int , int > lis = new Dictionary< int , int >(); // Adding value for N=4 in Hash Map lis[0] = 2; lis[1] = 1; lis[2] = 4; lis[3] = 3; int i = 3; int idx = 0; if (N >= 6) { i++; idx--; // Adding new N at starting index // and N-1 at last index int val = 5; while (val <= N) { lis[i] = val; lis[idx] = val + 1; idx -= 1; i += 1; val += 2; } } // Creating Array List // which will use to form // required array List< int > al = new List< int >(); // Traversing from minimum key // to maximum key add // adding its value in Array List for ( int j = idx + 1; j < i; j++) { al.Add(lis[j]); } // Returning formed array return al; } } } // This code is contributed by ukasp. |
Javascript
// Function to create array having same LIS from both sides function equalLIS(N) { // If N = 2 we can't create array if (N === 2) { let al = []; al.push(-1); return al; } // If N is odd it is possible to make an array else if (N % 2 !== 0) { // Object that contains index with its value let lis = {}; // indices 0, N/2, and N-1 lis[0] = 1; lis[N - 1] = 2; let mid = Math.floor(N / 2); lis[mid] = N; if (N > 3) { // Adding numbers 3, 4, ... and so on at index from 1 to mid-1 // respectively let val = 3; for (let i = 1; i < mid; i++) { lis[i] = val; val++; } // Adding remaining integers in decreasing order from mid+1 to N-2 val = N - 1; for (let i = mid + 1; i < N - 1; i++) { lis[i] = val; val--; } } // Array that will be used to form the required array let al = []; // Traversing from smallest key to largest key in Object // and adding its value in the array for (let i = 0; i < N; i++) { al.push(lis[i]); } // Returning the formed array return al; } else { // Object that contains index with its value let lis = {}; // Adding value for N = 4 in Object lis[0] = 2; lis[1] = 1; lis[2] = 4; lis[3] = 3; let i = 3; let idx = 0; if (N >= 6) { i++; idx--; // Adding new N at starting index and N-1 at last index let val = 5; while (val <= N) { lis[i] = val; lis[idx] = val + 1; idx--; i++; val += 2; } } // Array that will be used to form the required array let al = []; // Traversing from minimum key to maximum key and adding // its value in the array for (let j = idx + 1; j < i; j++) { al.push(lis[j]); } // Returning the formed array return al; } } // Driver code let N = 7; let lis = equalLIS(N); console.log(lis.join( " " )); //This code is contributed by Edula Vinay Kumar Reddy |
1 3 4 7 6 5 2
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us