Max count of N using digits of M such that 2 and 5 , and , 6 and 9 can be treated as same respectively | C ++ program for the above approach ; Function to find the count of numbers that can be formed using the given digits in the string ; Store the frequency of digits from the given string M ; Store length of the string M ; Loop to traverse the string ; Replace 5 with 2 ; Replace 9 with 6 ; Get the int form of the current character in the string ; Insert in the map ; Store all the digits of the required number N ; Loop to get all the digits from the number N ; Get the last digit as the remainder ; Replace 5 with 2 ; Replace 9 with 6 ; Insert the remainders in the rems map ; Store the resultant count ; Iterate through the rems map ; Get the key which is a digit from the number N to be formed ; If not present in the string M , number N that cannot be formed ; Divide the frequency of the digit from the string M with the frequency of the current remainder ; Choose the minimum ; Return the maximum count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int solve ( int n , string str ) { map < int , int > mymap ; int len = str . size ( ) ; for ( int i = 0 ; i < len ; i ++ ) { char c = str [ i ] ; if ( c == '5' ) c = '2' ; else if ( c == '9' ) c = '6' ; int c_int = c - ' a ' ; if ( mymap . find ( c_int ) != mymap . end ( ) ) mymap [ c_int ] += 1 ; else mymap [ c_int ] = 1 ; } map < int , int > rems ; while ( n > 0 ) { int rem = n % 10 ; if ( rem == 5 ) rem = 2 ; if ( rem == 9 ) rem = 6 ; if ( rems . find ( rem ) != rems . end ( ) ) rems [ rem ] += 1 ; else rems [ rem ] = 1 ; n = n / 10 ; } int cnt = 1e8 ; for ( auto ele : rems ) { int key = ele . first ; if ( mymap . find ( key ) == mymap . end ( ) ) return 0 ; int temp = mymap [ key ] / ele . second ; cnt = min ( cnt , temp ) ; } return cnt ; } int main ( ) { int N = 56 ; string M = "245769" ; cout << solve ( N , M ) << endl ; return 0 ; }