En utilisant les nombres M, le nombre maximum est N, où 2 et 5 et 6 et 9 peuvent être considérés comme identiques.

Le nombre maximum est un nombre maximum possible. Ici, on nous donne un entier N et une chaîne d’entier M. Notre tâche est de former le nombre N en utilisant les chiffres de l'entier M et de renvoyer le nombre maximum. En même temps, nous pouvons considérer 2 et 5 comme le même nombre, et 6 et 9 comme le même nombre.

Exemple d'exemple

Entrez 1

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

Explication − Puisque 5 et 2 sont identiques et que 6 et 9 sont identiques, nous avons deux '2 et deux '9. Par conséquent, le nombre maximum d’utilisation des chiffres de la chaîne M (2596783) pour former le nombre N (29) est de 2.

Entrez 2

N = 999
M = 6666925
Output 2: 1

Méthode

Discutons de la méthode ci-dessous étape par étape-

• Tout d'abord, nous allons créer une fonction appelée « maxCountOfN » qui prendra la chaîne « M » et le nombre « N » donnés comme paramètres et renverra l'entier requis « maxCount » comme valeur de retour.

• Dans cette fonction, nous allons créer une carte de hachage 'mp' pour stocker la fréquence de chaque nombre dans la chaîne 'M'.

• Nous définissons une variable 'len' pour stocker la taille de la chaîne 'M'.

• Parcourez la chaîne 'M' à partir de l'index 'i = 0' jusqu'à ce qu'elle soit inférieure ou égale à 'len', et effectuez les opérations suivantes sous cette boucle :

• Si le nombre que nous obtenons est « 2 », nous le convertissons en « 5 ».

• Si nous obtenons un nombre « 6 », nous le convertissons en « 9 ».

• Comptez la fréquence de chaque nombre dans la carte « mp » comme une paire caractère-entier.

• Créez une autre carte de hachage 'mpN' pour stocker la fréquence du numéro N

• Utilisez une boucle while pour parcourir le nombre « N » jusqu'à ce que N soit supérieur à 0, et effectuez les opérations suivantes sous cette boucle -

• Créez un entier « rem » pour stocker le dernier élément du nombre

• Vérifiez si c'est 2 et convertissez-le en 5

• Vérifiez si rem est 6 et convertissez-le en 9

• Comptez la fréquence de chaque nombre dans la carte « mpN » sous forme de paires de caractères-entiers. Il s'agit de stocker l'entier sous forme de caractère dans la carte, comme 'mpN[rem + '0']'.

• Réduisez N à N%10 pour supprimer le dernier chiffre du numéro

• Nous créons une variable 'maxCount' qui stocke 'INT_MAX'.

• Enfin, nous parcourons la carte 'mpN' pour trouver le nombre maximum de N et faisons ce qui suit sous cette boucle -

• Stocker le nombre de chiffres dans la variable « clé »

• Vérifiez si la clé existe dans le plan des chaînes, si elle n'est pas présente cela signifie que nous ne pouvons pas créer le nombre 'N' en utilisant les numéros de la chaîne 'M', nous renvoyons '0'.

• Créez une variable dans la variable 'tempCount' où nous stockons la valeur (en divisant la fréquence des nombres dans la chaîne M par la fréquence actuelle des nombres dans N).

• Dans maxCount, nous stockons la valeur minimale de tempCount et maxCount car il est possible de générer le nombre 'N' uniquement si chaque chiffre du nombre 'N' apparaît dans la chaîne 'M'

• Retour maxCount

La traduction chinoise de

Exemple

est :

Exemple

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

Sortie

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

Conclusion

Dans ce tutoriel, nous avons implémenté un programme pour trouver le nombre maximum de N en utilisant les chiffres de M tels que 2 et 5, et 6 et 9 peuvent être traités comme identiques respectivement. Nous avons implémenté une approche de hachage comme nous l'avons fait. pour stocker la fréquence avec la complexité temporelle de O(N+M) et la complexité spatiale de O(N+M) Où M est la taille de la chaîne et N est la taille du nombre.

.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!