Lexicographically smallest permutation of length 2 N that can be obtained from an N | C ++ program for the above approach ; Function to find the lexicographically smallest permutation of length 2 * N satisfying the given conditions ; Stores if i - th element is placed at odd position or not ; Traverse the array ; Mark arr [ i ] true ; Stores all the elements not placed at odd positions ; Iterate in the range [ 1 , 2 * N ] ; If w [ i ] is not marked ; Stores whether it is possible to obtain the required permutation or not ; Stores the permutation ; Traverse the array arr [ ] ; Finds the iterator of the smallest number greater than the arr [ i ] ; If it is S . end ( ) ; Mark found false ; Push arr [ i ] and * it into the array ; Erase the current element from the Set ; If found is not marked ; Otherwise , ; Print the permutation ; Driver Code ; Given Input ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void smallestPermutation ( int arr [ ] , int N ) { vector < bool > w ( 2 * N + 1 ) ; for ( int i = 0 ; i < N ; i ++ ) { w [ arr [ i ] ] = true ; } set < int > S ; for ( int i = 1 ; i <= 2 * N ; i ++ ) { if ( ! w [ i ] ) S . insert ( i ) ; } bool found = true ; vector < int > P ; for ( int i = 0 ; i < N ; i ++ ) { auto it = S . lower_bound ( arr [ i ] ) ; if ( it == S . end ( ) ) { found = false ; break ; } P . push_back ( arr [ i ] ) ; P . push_back ( * it ) ; S . erase ( it ) ; } if ( ! found ) { cout << " - 1 STRNEWLINE " ; } else { for ( int i = 0 ; i < 2 * N ; i ++ ) cout << P [ i ] << " ▁ " ; } } int main ( ) { int arr [ ] = { 4 , 1 , 3 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; smallestPermutation ( arr , N ) ; return 0 ; }