Lexicographically smallest permutation number up to K having given array as a subsequence | Java program for the above approach ; Function to find the lexicographically smallest permutation such that the given array is a subsequence of it ; Stores the missing elements in arr in the range [ 1 , K ] ; Stores if the ith element is present in arr or not ; Loop to mark all integers present in the array as visited ; Loop to insert all the integers not visited into missing ; Append Integer . MAX_VALUE at end in order to prevent going out of bounds ; Pointer to the current element ; Pointer to the missing element ; Stores the required permutation ; Loop to conthe permutation using greedy approach ; If missing element is smaller that the current element insert missing element ; Insert current element ; Print the required Permutation ; Driver Code ; Function Call
import java . util . * ; class GFG { static void findPermutation ( int K , Vector < Integer > arr ) { Vector < Integer > missing = new Vector < Integer > ( ) ; boolean visited [ ] = new boolean [ K + 1 ] ; for ( int i = 0 ; i < arr . size ( ) ; i ++ ) { visited [ arr . get ( i ) ] = true ; } for ( int i = 1 ; i <= K ; i ++ ) { if ( ! visited [ i ] ) { missing . add ( i ) ; } } arr . add ( Integer . MAX_VALUE ) ; missing . add ( Integer . MAX_VALUE ) ; int p1 = 0 ; int p2 = 0 ; Vector < Integer > ans = new Vector < Integer > ( ) ; while ( ans . size ( ) < K ) { if ( arr . get ( p1 ) < missing . get ( p2 ) ) { ans . add ( arr . get ( p1 ) ) ; p1 ++ ; } else { ans . add ( missing . get ( p2 ) ) ; p2 ++ ; } } for ( int i = 0 ; i < K ; i ++ ) { System . out . print ( ans . get ( i ) + " ▁ " ) ; } } public static void main ( String [ ] args ) { int K = 7 ; Integer [ ] a = { 6 , 4 , 2 , 1 } ; Vector < Integer > arr = new Vector < > ( Arrays . asList ( a ) ) ; findPermutation ( K , arr ) ; } }