Largest number not exceeding N that does not contain any of the digits of S | C ++ program to implement the above approach ; Function to obtain the largest number not exceeding num which does not contain any digits present in S ; Stores digits of S ; Traverse the string S ; Set occurrence as true ; Traverse the string n ; All digits of num are not present in string s ; Largest Digit not present in the string s ; Set all digits from positions in + 1 to n - 1 as LargestDig ; Counting leading zeroes ; Removing leading zeroes ; If the string becomes null ; Return the largest number ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; string greatestReducedNumber ( string num , string s ) { vector < bool > vis_s ( 10 , false ) ; for ( int i = 0 ; i < ( int ) s . size ( ) ; i ++ ) { vis_s [ int ( s [ i ] ) - 48 ] = true ; } int n = num . size ( ) ; int in = -1 ; for ( int i = 0 ; i < n ; i ++ ) { if ( vis_s [ ( int ) num [ i ] - '0' ] ) { in = i ; break ; } } if ( in == -1 ) { return num ; } for ( char dig = num [ in ] ; dig >= '0' ; dig -- ) { if ( vis_s [ ( int ) dig - '0' ] == 0 ) { num [ in ] = dig ; break ; } } char LargestDig = '0' ; for ( char dig = '9' ; dig >= '0' ; dig -- ) { if ( vis_s [ dig - '0' ] == false ) { LargestDig = dig ; break ; } } for ( int i = in + 1 ; i < n ; i ++ ) { num [ i ] = LargestDig ; } int Count = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( num [ i ] == '0' ) Count ++ ; else break ; } num . erase ( 0 , Count ) ; if ( ( int ) num . size ( ) == 0 ) return "0" ; return num ; } int main ( ) { string N = "12345" ; string S = "23" ; cout << greatestReducedNumber ( N , S ) ; return 0 ; }