Find Kth lexicographical ordered numeric string of length N with distinct products of each substring | C ++ program for the above approach ; Function to find the required string ; If the current length is equal to n exit from here only ; Iterate for all the characters ; Check if the product is present before ; If the current string is good then recurse for the next character ; Decrease all the products back to their original state ; Erase the last character ; Function to calculate kth ordered valid string ; Check for the base cases ; There are atmost 10 valid strings for n = 1 ; Vector to keep a check on number of occurences of products ; Recursively construct the strings ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void getString ( int curlen , string & ans , string & s , int N , int & K , vector < int > & prod ) { if ( curlen == N ) { K -- ; if ( K == 0 ) ans = s ; return ; } char ch ; int ok , t , i ; for ( ch = '2' ; ch <= '9' ; ch ++ ) { s += ch ; ok = 1 ; t = 1 ; for ( i = curlen ; i >= 0 ; i -- ) { t *= s [ i ] - 48 ; if ( prod [ t ] ) ok = 0 ; prod [ t ] ++ ; } if ( ok ) getString ( curlen + 1 , ans , s , N , K , prod ) ; t = 1 ; for ( i = curlen ; i >= 0 ; i -- ) { t *= s [ i ] - 48 ; prod [ t ] -- ; } s . erase ( s . length ( ) - 1 ) ; } } string kthValidString ( int N , int K ) { if ( N > 10 ) { return " - 1" ; } if ( N == 1 ) { if ( K > 10 ) { return " - 1" ; } string s = " " ; K -- ; s += ( K + '0' ) ; return s ; } string ans = " - 1" ; string s = " " ; vector < int > prod ( 10005 , 0 ) ; getString ( 0 , ans , s , N , K , prod ) ; return ans ; } int main ( ) { int N = 3 , K = 4 ; cout << kthValidString ( N , K ) ; }