Max count是一个可能的最大计数。在这里，我们给出了一个整数N和一个整数M的字符串。我们的任务是使用整数M的数字来组成数字N，并返回最大计数。同时，我们可以将2和5视为同一个数字，将6和9视为同一个数字。

样例示例

输入 1

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

解释 − 因为5和2相同，6和9相同，所以我们有两个'2'和两个'9'。因此，使用字符串M（2596783）的数字来组成数字N（29）的最大计数是2。

输入2

N = 999
M = 6666925
Output 2: 1

方法

让我们逐步讨论下面的方法-

• 首先，我们将创建一个名为‘maxCountOfN’的函数，该函数将以给定的字符串‘M’和数字‘N’作为参数，并将返回所需的整数‘maxCount’作为返回值。

• 在该函数中，我们将创建一个哈希映射 'mp' 来存储字符串 'M' 中每个数字的频率。

• 我们定义一个变量‘len’来存储字符串‘M’的大小。

• 从索引‘i = 0’开始遍历字符串‘M’，直到小于等于‘len’，并在此循环下执行以下操作：

• 如果我们得到的数字是‘2’，我们将其转换为‘5’。

• 如果我们得到一个数字为‘6’，我们将其转换为‘9’。

• 统计'mp'映射中每个数字的频率作为字符-整数对。

• 创建另一个哈希映射 'mpN' 以存储数字 N 的频率

• 使用while循环遍历数字‘N’，直到N大于0，并在此循环下执行以下操作 -

• 创建一个整数‘rem’来存储数字的最后一个元素

• 检查是否为2并将其转换为5

• 检查 rem 是否为 6 并将其转换为 9

• 将'mpN'映射中每个数字的频率计数为字符-整数对。即将整数作为字符存储在映射中，如'mpN[rem + '0']'。

• 将 N 减少到 N%10，以去除数字的最后一位

• 我们创建一个变量 'maxCount'，其中存储 'INT_MAX'。

• 最后，我们遍历地图 'mpN' 来找到 N 的最大计数，并在此循环下执行以下操作 -

• 在变量‘key’中存储数字的位数

• 检查键是否存在于字符串的映射中，如果不存在意味着我们无法使用字符串'M'的数字创建数字'N'，我们返回'0'。

• 在变量'tempCount'中创建一个变量，我们将值存储在其中（将字符串M中的数字频率除以N的当前数字频率）。

• 在maxCount中，我们存储tempCount和maxCount的最小值，因为只有当数字'N'的每个数字都出现在字符串'M'中时，才可能生成数字'N'

• Return maxCount

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;
}

输出

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

结论

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.