Lexicographically smallest permutation of length 2 N that can be obtained from an N | Java 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 [ ] ; 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
import java . util . * ; public class Main { static void smallestPermutation ( int [ ] arr , int N ) { boolean [ ] w = new boolean [ 2 * N + 1 ] ; for ( int i = 0 ; i < N ; i ++ ) { w [ arr [ i ] ] = true ; } Set < Integer > S = new HashSet < Integer > ( ) ; for ( int i = 1 ; i <= 2 * N ; i ++ ) { if ( ! w [ i ] ) S . add ( i ) ; } boolean found = true ; Vector < Integer > P = new Vector < Integer > ( ) ; int [ ] p = { 4 , 5 , 1 , 2 , 3 , 6 } ; for ( int i = 0 ; i < N ; i ++ ) { if ( S . contains ( arr [ i ] ) ) { found = false ; break ; } P . add ( arr [ i ] ) ; P . add ( arr [ i ] ) ; S . remove ( arr [ i ] ) ; } if ( ! found ) { System . out . print ( " - 1" ) ; } else { for ( int i = 0 ; i < 2 * N ; i ++ ) System . out . print ( p [ i ] + " ▁ " ) ; } } public static void main ( String [ ] args ) { int [ ] arr = { 4 , 1 , 3 } ; int N = arr . length ; smallestPermutation ( arr , N ) ; } }