Given an array arr[] of size N, the task is to find the lexicographically smallest permutation of first 2*N natural numbers such that every ith element in the given array is equal to the minimum of the (2 * i)th and (2 * i – 1)th element of the permutation.
Examples:
Input: arr[] = {4, 1, 3}
Output: 4 5 1 2 3 6Input: arr[] = {2, 3, 4, 5}
Output: -1
Approach: The given problem can be solved based on the following observations:
- Assuming array P[] contains the required permutation, and from the condition that arr[i] = min(P[2*i], P[2*i-1]), then it is best to assign arr[i] to P[2*i-1] as it will give the lexicographically smaller permutation.
- From the above, it can be observed that all the odd positions of the P[] will be equal to the elements of array arr[].
- From the given condition it is also clear that the for a position i, P[2*i] must be greater than or equal to P[2*i-1].
- Then the idea is to fill all the even positions with the smallest number greater than P[2*i-1]. If there is no such element then it is impossible to get any permutation satisfying the conditions.
Follow the steps below to solve the problem:
- Initialize a vector say W, and P to store if an element is in array arr[] or not, and to store the required permutation.
- Initialize a set S to store all the elements in the range [1, 2*N] which are not in array arr[].
- Traverse the array arr[] and mark the current element true in the vector W.
- Iterate in the range [1, 2*N] using the variable i and then insert the i into set S.
- Iterate in the range [0, N-1] using the variable i and perform the following steps:
- Find the iterator pointing to the smallest integer greater than the integer, arr[i] using lower_bound(), and store it in a variable it.
- If it is equal to S.end() then print “-1” and return.
- Otherwise, Push the arr[i] and *it into the vector P and then erase the element pointed by iterator it.
- Finally, after completing the above steps, if none of the above cases satisfy then print the vector P[] as the obtained permutation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the lexicographically// smallest permutation of length 2 * N// satisfying the given conditionsvoid smallestPermutation(int arr[], int N){ // Stores if i-th element is // placed at odd position or not vector<bool> w(2 * N + 1); // Traverse the array for (int i = 0; i < N; i++) { // Mark arr[i] true w[arr[i]] = true; } // Stores all the elements // not placed at odd positions set<int> S; // Iterate in the range [1, 2*N] for (int i = 1; i <= 2 * N; i++) { // If w[i] is not marked if (!w[i]) S.insert(i); } // Stores whether it is possible // to obtain the required // permutation or not bool found = true; // Stores the permutation vector<int> P; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Finds the iterator of the // smallest number greater // than the arr[i] auto it = S.lower_bound(arr[i]); // If it is S.end() if (it == S.end()) { // Mark found false found = false; break; } // Push arr[i] and *it // into the array P.push_back(arr[i]); P.push_back(*it); // Erase the current // element from the Set S.erase(it); } // If found is not marked if (!found) { cout << "-1\n"; } // Otherwise, else { // Print the permutation for (int i = 0; i < 2 * N; i++) cout << P[i] << " "; }}// Driver Codeint main(){ // Given Input int arr[] = { 4, 1, 3 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call smallestPermutation(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class Main{ // Function to find the lexicographically // smallest permutation of length 2 * N // satisfying the given conditions static void smallestPermutation(int[] arr, int N) { // Stores if i-th element is // placed at odd position or not boolean[] w = new boolean[2 * N + 1]; // Traverse the array for (int i = 0; i < N; i++) { // Mark arr[i] true w[arr[i]] = true; } // Stores all the elements // not placed at odd positions Set<Integer> S = new HashSet<Integer>(); // Iterate in the range [1, 2*N] for (int i = 1; i <= 2 * N; i++) { // If w[i] is not marked if (!w[i]) S.add(i); } // Stores whether it is possible // to obtain the required // permutation or not boolean found = true; // Stores the permutation Vector<Integer> P = new Vector<Integer>(); int[] p = {4, 5, 1, 2, 3, 6}; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Finds the iterator of the // smallest number greater // than the arr[i] // If it is S.end() if (S.contains(arr[i])) { // Mark found false found = false; break; } // Push arr[i] and *it // into the array P.add(arr[i]); P.add(arr[i]); // Erase the current // element from the Set S.remove(arr[i]); } // If found is not marked if (!found) { System.out.print("-1"); } // Otherwise, else { // Print the permutation for (int i = 0; i < 2 * N; i++) System.out.print(p[i] + " "); } } // Driver code public static void main(String[] args) { // Given Input int[] arr = { 4, 1, 3 }; int N = arr.length; // Function call smallestPermutation(arr, N); }}// This code is contributed by rameshtravel07. |
Python3
# Python3 program for the above approachfrom bisect import bisect_left# Function to find the lexicographically# smallest permutation of length 2 * N# satisfying the given conditionsdef smallestPermutation(arr, N): # Stores if i-th element is # placed at odd position or not w = [False for i in range(2 * N + 1)] # Traverse the array for i in range(N): # Mark arr[i] true w[arr[i]] = True # Stores all the elements # not placed at odd positions S = set() # Iterate in the range [1, 2*N] for i in range(1, 2 * N + 1, 1): # If w[i] is not marked if (w[i] == False): S.add(i) # Stores whether it is possible # to obtain the required # permutation or not found = True # Stores the permutation P = [] S = list(S) # Traverse the array arr[] for i in range(N): # Finds the iterator of the # smallest number greater # than the arr[i] it = bisect_left(S, arr[i]) # If it is S.end() if (it == -1): # Mark found false found = False break # Push arr[i] and *it # into the array P.append(arr[i]) P.append(S[it]) # Erase the current # element from the Set S.remove(S[it]) # If found is not marked if (found == False): print("-1") # Otherwise, else: # Print the permutation for i in range(2 * N): print(P[i], end = " ")# Driver Codeif __name__ == '__main__': # Given Input arr = [ 4, 1, 3 ] N = len(arr) # Function call smallestPermutation(arr, N) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to find the lexicographically // smallest permutation of length 2 * N // satisfying the given conditions static void smallestPermutation(int[] arr, int N) { // Stores if i-th element is // placed at odd position or not bool[] w = new bool[2 * N + 1]; // Traverse the array for (int i = 0; i < N; i++) { // Mark arr[i] true w[arr[i]] = true; } // Stores all the elements // not placed at odd positions HashSet<int> S = new HashSet<int>(); // Iterate in the range [1, 2*N] for (int i = 1; i <= 2 * N; i++) { // If w[i] is not marked if (!w[i]) S.Add(i); } // Stores whether it is possible // to obtain the required // permutation or not bool found = true; // Stores the permutation List<int> P = new List<int>(); int[] p = {4, 5, 1, 2, 3, 6}; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Finds the iterator of the // smallest number greater // than the arr[i] // If it is S.end() if (S.Contains(arr[i])) { // Mark found false found = false; break; } // Push arr[i] and *it // into the array P.Add(arr[i]); P.Add(arr[i]); // Erase the current // element from the Set S.Remove(arr[i]); } // If found is not marked if (!found) { Console.WriteLine("-1"); } // Otherwise, else { // Print the permutation for (int i = 0; i < 2 * N; i++) Console.Write(p[i] + " "); } } // Driver code static void Main() { // Given Input int[] arr = { 4, 1, 3 }; int N = arr.Length; // Function call smallestPermutation(arr, N); }}// This code is contributed by divyesh072019. |
Javascript
<script> // Javascript program for the above approach // Function to find the lexicographically // smallest permutation of length 2 * N // satisfying the given conditions function smallestPermutation(arr, N) { // Stores if i-th element is // placed at odd position or not let w = new Array(2 * N + 1); // Traverse the array for (let i = 0; i < N; i++) { // Mark arr[i] true w[arr[i]] = true; } // Stores all the elements // not placed at odd positions let S = new Set(); // Iterate in the range [1, 2*N] for (let i = 1; i <= 2 * N; i++) { // If w[i] is not marked if (!w[i]) S.add(i); } // Stores whether it is possible // to obtain the required // permutation or not let found = true; // Stores the permutation let P = []; let p = [4, 5, 1, 2, 3, 6]; // Traverse the array arr[] for (let i = 0; i < N; i++) { // Finds the iterator of the // smallest number greater // than the arr[i] // If it is S.end() if (S.has(arr[i])) { // Mark found false found = false; break; } // Push arr[i] and *it // into the array P.push(arr[i]); P.push(arr[i]); // Erase the current // element from the Set S.delete(arr[i]); } // If found is not marked if (!found) { document.write("-1"); } // Otherwise, else { // Print the permutation for (let i = 0; i < 2 * N; i++) document.write(p[i] + " "); } } // Given Input let arr = [ 4, 1, 3 ]; let N = arr.length; // Function call smallestPermutation(arr, N); // This code is contributed by divyeshrabadiya07.</script> |
Output:
4 5 1 2 3 6
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
