Pour rendre un nombre divisible par 4, le nombre minimum de chiffres à supprimer

Dans cet article, nous explorerons un problème de calcul intéressant : "Le nombre minimum de chiffres qui doivent être supprimés pour rendre un nombre divisible par 4". Cette question est une question fréquemment posée lors des concours de codage et des entretiens basés sur des algorithmes et constitue une excellente pratique pour améliorer vos compétences en résolution de problèmes.

Tout d’abord, comprenons l’énoncé du problème : nous avons un nombre et notre tâche est de supprimer le nombre minimum de chiffres afin que le nombre restant soit divisible par 4.

Compréhension conceptuelle

Le problème réside dans le domaine de la théorie des nombres. Un fait clé à comprendre est qu’un nombre est divisible par 4 si et seulement si ses deux derniers chiffres sont divisibles par 4. Ce fait est crucial pour résoudre notre problème.

Description de l'algorithme

L'algorithme pour résoudre ce problème implique les étapes suivantes -

• Convertissez les nombres en chaînes.

• Commencez par la fin de la chaîne et vérifiez si le nombre composé des deux derniers caractères est divisible par 4.

• Si oui, renvoyez le nombre de chiffres supprimés. Sinon, supprimez le dernier caractère et incrémentez le nombre.

• Répétez cette opération jusqu'à ce que le nombre soit divisible par 4 ou qu'il ne reste qu'un seul chiffre.

Exemple

Il s'agit d'une implémentation C++ de l'algorithme -

#include<bits/stdc++.h>
using namespace std;

int minRemovals(string num) {
   int n = num.size();
   int count = 0;
   
   for (int i = n - 1; i > 0; i--) {
      if ((num[i] - '0' + (num[i - 1] - '0') * 10) % 4 == 0) {
         return count;
      }
      count++;
   }
   
   return n - 1;
}

int main() {
   string num = "1351";
   cout << "Minimum number of digits to be removed to make the number divisible by 4 is: ";
   cout << minRemovals(num) << endl;
   
   return 0;
}

Sortie

Minimum number of digits to be removed to make the number divisible by 4 is: 3

Dans la fonction minRemovals, nous initialisons le compteur à 0, ce qui permettra de garder une trace du nombre de bits supprimés. Nous parcourons ensuite à partir de la fin du nombre (chaîne) et vérifions si les deux derniers chiffres forment un nombre divisible par 4. Si tel est le cas, nous renvoyons le décompte ; sinon, nous renvoyons le décompte. Sinon, nous incrémentons le décompte et passons à l'itération suivante.

La fonction

main sert de point d'entrée à notre programme où nous définissons le numéro d'entrée et imprimons le nombre minimum de chiffres à supprimer pour que le nombre soit divisible par 4.

Exemple de cas de test

Prenons le nombre 1351 comme exemple. Quand on examine les deux derniers chiffres (51), on voit qu'il n'est pas divisible par 4. Par conséquent, nous supprimons le dernier chiffre (1) et obtenons le nombre 135. Nous vérifions à nouveau et constatons que les deux derniers chiffres (35) ne sont toujours pas divisibles par 4. Par conséquent, nous supprimons le dernier chiffre (5), laissant le nombre 13. Les deux derniers chiffres (13) ne sont pas divisibles par 4, on supprime donc le dernier chiffre (3). Il nous reste maintenant le chiffre 1, qui n'est pas divisible par 4, mais nous ne pouvons plus supprimer de chiffres. Par conséquent, le nombre minimum de chiffres à supprimer est de 3.

Complexité temporelle et spatiale

La complexité temporelle de cet algorithme est O(n), où n est le nombre de chiffres du nombre. La complexité spatiale est O(1) puisque nous n'utilisons aucune structure de données supplémentaire dans l'algorithme.

Conclusion

Dans cet article, nous abordons un problème informatique courant : déterminer le nombre minimum de chiffres qui doivent être supprimés pour rendre un nombre divisible par 4. Nous avons développé une solution C++ concise en utilisant les informations clés de la théorie des nombres.

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!