Using numbers of M, the maximum count is N, where 2 and 5 and 6 and 9 can be considered the same as each other

Max count is the maximum possible count. Here, we are given an integer N and a string of integer M. Our task is to form the number N using the digits of the integer M and return the maximum count. At the same time, we can think of 2 and 5 as the same number, and 6 and 9 as the same number.

Sample Example

Enter 1

N = 29
M = "2569783"
Output 1: 2

Explanation − Since 5 and 2 are the same and 6 and 9 are the same, we have two '2's and two '9's. Therefore, the maximum count of using the digits of the string M (2596783) to form the number N (29) is 2.

Enter 2

N = 999
M = 6666925
Output 2: 1

method

Let us discuss the following method step by step -

• First, we will create a function called 'maxCountOfN' which will take the given string 'M' and number 'N' as parameters and will return the required integer 'maxCount' as return value.

• In this function, we will create a hash map 'mp' to store the frequency of each number in the string 'M'.

• We define a variable 'len' to store the size of string 'M'.

• Traverse the string 'M' starting from index 'i = 0' until it is less than or equal to 'len', and perform the following operations under this loop:

• If the number we get is '2', we convert it to '5'.

• If we get a number as '6', we convert it to '9'.

• Count the frequency of each number in the 'mp' map as a character-integer pair.

• Create another hash map 'mpN' to store the frequency of the number N

• Use a while loop to traverse the number 'N' until N is greater than 0, and perform the following operations under this loop -

• Create an integer 'rem' to store the last element of the number

• Check if it is 2 and convert it to 5

• Check if rem is 6 and convert it to 9

• Count the frequency of each digit in the 'mpN' map as a character-integer pair. That is, the integer is stored in the map as a character, such as 'mpN[rem '0']'.

• Reduce N to N to remove the last digit of the number

• We create a variable 'maxCount', which stores 'INT_MAX'.

• Finally, we loop through the map 'mpN' to find the maximum count of N and do the following under this loop -

• Storing the number of digits in the variable ‘key’

• Check if the key exists in the map of strings, if not present it means we cannot create the number 'N' using the numbers of the string 'M', we return '0'.

• Create a variable in the variable 'tempCount' in which we store the value (the frequency of numbers in string M divided by the current frequency of numbers in N).

• In maxCount, we store the minimum value of tempCount and maxCount, because it is possible to generate the number 'N' only when every digit of the number 'N' appears in the string 'M'

• Return maxCount

The Chinese translation of

Example

is:

Example

#include <bits/stdc++.h>
using namespace std;
int maxCountOfN(int N, string M){
   map< char, int >mp; //created hashmap to store the frequency of each digit of //string
   int len = M.size(); // getting the size of the string     
   // iterating string using for loop 
   for(int i=0;i<len;i++){
      if(M[i] == '2'){
         M[i] = '5'; // replace 2 with 5
      }
      else if(M[i] == '6'){ 
         M[i] = '9'; // replace 6 with 9
      }
      mp[M[i]]++; //count frequency of digit of string
   }    
   // creating another hashmap to store the frequency of digit of the number N
   map<char, int>mpN;      
   // iterating number 'N' using while loop     
   while(N > 0){
      int rem = N % 10; // Get the last digit as the remainder        
      //Replace 2 with 5
      if(rem == 2){
         rem = 5;
      }
      //Replace 6 with 9
      if(rem == 6){
         rem = 9;
      }        
      mpN[rem + '0']++; //count frequency of digit of number        
      N = N / 10;
   }    
   int maxCount = INT_MAX;
   //Trvaerse the hashmap of the number to get the maxCount
   for(auto el : mpN){
      // Get the key which is a digit from the number N to be formed
      int key = el.first; 
      // If the key is not present in the string M, then the number N cannot be formed
      if (!mp.count(key))
      return 0; 
      // Divide the frequency of the digit from the string M with the frequency of the current digit of N
      int tempCount = mp[key] / el.second; 
      // Choose the minimum
      maxCount = min(maxCount, tempCount);
   }    
   // returning the maximum count 
   return maxCount;
}
// main function 
int main(){    
   int N = 29; // given number
   string M = "2569783";// given string    
   // calling the function to get a maximum count of N 
   int maxCount = maxCountOfN(N, M);   
   cout<<"The max count of making the number "<< N << " using the digits of the string " << M << " is "<< maxCount<<endl;   
   return 0;
}

Output

The max count of making the number 29 using the digits of the string 2569783 is 2

in conclusion

In this tutorial, we have implemented a program to find the Max count of N using digits of M such that 2 and 5, and, 6 and 9 can be treated as the same respectively. We have implemented an approach of hashing as we have to store the frequency with the time complexity of O(N M) and space complexity of O(N M). Where M is the size of the string and N is the size of the Number.

The above is the detailed content of Using numbers of M, the maximum count is N, where 2 and 5 and 6 and 9 can be considered the same as each other. For more information, please follow other related articles on the PHP Chinese website!