Lexicographically smallest permutation number up to K having given array as a subsequence | C ++ 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 INT_MAX 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 construct the 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findPermutation ( int K , vector < int > arr ) { vector < int > missing ; vector < bool > visited ( K + 1 , 0 ) ; for ( int i = 0 ; i < arr . size ( ) ; i ++ ) { visited [ arr [ i ] ] = 1 ; } for ( int i = 1 ; i <= K ; i ++ ) { if ( ! visited [ i ] ) { missing . push_back ( i ) ; } } arr . push_back ( INT_MAX ) ; missing . push_back ( INT_MAX ) ; int p1 = 0 ; int p2 = 0 ; vector < int > ans ; while ( ans . size ( ) < K ) { if ( arr [ p1 ] < missing [ p2 ] ) { ans . push_back ( arr [ p1 ] ) ; p1 ++ ; } else { ans . push_back ( missing [ p2 ] ) ; p2 ++ ; } } for ( int i = 0 ; i < K ; i ++ ) { cout << ans [ i ] << " ▁ " ; } } int main ( ) { int K = 7 ; vector < int > arr = { 6 , 4 , 2 , 1 } ; findPermutation ( K , arr ) ; return 0 ; }