Programme C++ pour supprimer des caractères d'une chaîne numérique afin qu'elle soit divisible par 8

Étant donné un nombre sous la forme d'une chaîne, nous devons trouver où le rendre divisible par huit après avoir supprimé zéro ou plusieurs éléments. En d'autres termes, nous devons trouver s'il existe une sous-séquence de la chaîne, ce qui est le cas. est divisible par 8. Renvoie la chaîne modifiée ou -1 si ce n'est pas possible.

Selon la règle de divisibilité, tout nombre dont les trois derniers chiffres sont divisibles par 8 est également divisible par 8. Par exemple, 56992992 et 476360 sont divisibles par 8, mais 2587788 ne l’est pas. Si le résultat est un nombre entier, le nombre d'origine est divisible par 8.

Regardons quelques scénarios d'entrée qui expliquent la méthode en détail −

Si l'entrée transmise à la méthode est une chaîne numérique contenant une sous-chaîne divisible par 8, alors dans la liste des résultats, nous pouvons obtenir la sous-chaîne divisible par 8−

Input: 2567992
Result: 56

Si l'entrée de la méthode est une chaîne numérique qui ne contient aucune sous-chaîne divisible par 8, la sortie sera renvoyée sous la forme −

Input: 77777777777
Result: -1

Algorithme

• L'entrée de chaîne est itérée, vérifiant si une sous-chaîne est un multiple de 8.

• S'il y a une sous-chaîne conséquente présente dans l'entrée, la sous-chaîne est renvoyée en sortie.

• Si la sous-chaîne est trouvée, le programme se termine, sinon répétez l'étape 2 jusqu'à ce que la sous-chaîne soit trouvée.

• S'il n'y a pas de sous-chaîne dans l'entrée divisible par 8, la sortie renvoyée est -1.

Exemple

Dans le programme C++ suivant, nous prenons deux chaînes, l'une peut être convertie en une chaîne divisible par 8 et l'autre ne le peut pas, et trouvons la sortie dans chaque cas. Nous pouvons parcourir de 0 à 1000 en multiples de 8 comme 0, 8, 16, 24, 32...1000 et vérifier si ce nombre existe en tant que sous-séquence de la chaîne donnée.

#include <iostream>
using namespace std;
int checkIfSubstringExist(string req, string given) {
   int index = 0;
   for (char ch : given) {
      if (req[index] == ch) {
         index++;
      }
   }
   return index == (int)req.size();
}
string solve(string s) {
   for (int i = 0; i < 1e3; i += 8) {
      string num = to_string(i);
      if (checkIfSubstringExist(num, s)) {
         return num;
      }
   }
   return "-1";
}
int main() {

   // the string “95256” can be converted to a string divisible by 8
   // the string “74516” cannot be converted to a string divisible by 8
   // let’s run our code to find the output in each case
   string s1 = "95258", s2="74516";
   cout << solve(s1) << "\n" << solve(s2) << endl;
   return 0;
}

Sortie

8
16

Comme vous pouvez le voir dans le résultat ci-dessus, 9525 est supprimé de 95258 et 745 est supprimé de 74516 pour rendre le nombre de gauche divisible par 8.

Conclusion

Comme on peut le voir, après une simple observation, il suffit de vérifier si le sous-ensemble existe. On vérifie si la chaîne contient une sous-séquence, dans le pire des cas elle vérifiera la chaîne entière. Par conséquent, si l’on nous donne une chaîne numérique de longueur n, la complexité temporelle dans le pire des cas est O(126*n), qui est O(n).

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!