Le moyen le plus rapide de trouver la somme des chiffres sur les grands nombres

Question

J'ai quelques gros chiffres (encore) et je dois trouver si la somme des chiffres est un nombre pair. J'ai essayé ceci: trouver la somme des chiffres avec une boucle while et ensuite vérifier si cette somme% 2 est égale à 0 et qu'elle fonctionne mais elle est trop lente pour les grands nombres, car on me donne des intervalles de nombres et si l'entrée est 1999999 19999999999 alors mon programme échoue, je ne peux pas terminer dans la limite de temps qui est de 0,1 sec.

Que faire? Y a-t-il un autre moyen plus rapide de le faire?

EDIT: L'entrée 1999999 19999999999 signifie qu'il commencera avec 1999999 et vérifiera tous les nombres comme j'ai écrit ci-dessus jusqu'à 19999999999, et parce que nous parlons des grands nombres (< 2^30) mon programme n'est pas digne.

Answer 1

Indice: si vous trouvez que la somme des chiffres d'un nombre donné n est impaire, la somme des chiffres du nombre n + 1 sera-t-elle pair ou impair?

Mise à jour: comme @ Mark a fait remarquer, il est si simple ... mais les anomalies apparaissent uniquement lorsque n + 1 est un multiple de 10, à savoir (n + 1) % 10 == 0. Alors la bizarrerie ne change pas. Cependant, sur ces cas, tous les dix sont une exception lorsque la singularité change encore (par exemple 199 -> 200). Et ainsi de suite ... en gros, selon où la valeur la plus élevée 9 de n est, on peut décider si l'étrangeté change entre n et n + 1. J'avoue que c'est un peu fastidieux à calculer, mais je suis sûr qu'il est plus rapide que de simplement additionner tous ces chiffres ...

Answer 2

Vous n'avez pas besoin d'additionner les chiffres. Penses-y. La somme commence par zéro, ce qui est généralement considéré comme pair (même si vous pouvez le cas particulier si vous le souhaitez).

Chaque chiffre pair ne change rien. Si la somme était étrange, elle reste étrange, même si elle reste égale.

Chaque chiffre impair change la somme de pair à impair, ou impair à pair.

Donc, il suffit de compter le nombre de chiffres impairs. Si le nombre est pair, alors la somme de tous les chiffres est pair. Si le nombre est impair, alors la somme de tous les chiffres est impaire.

Maintenant, il vous suffit de le faire pour le PREMIER numéro de votre gamme. Ce que vous devez faire ensuite est de comprendre comment l'uniformité ou l'étrangeté des nombres changent que vous continuez à en ajouter un. Je laisse cela comme un exercice pour le lecteur. Les devoirs doivent impliquer du travail!

Answer 3

Voici un indice, cela peut fonctionner - vous n'avez pas besoin d'additionner les chiffres dont vous avez besoin de savoir si le résultat sera pair ou impair - si vous partez de l'hypothèse que votre total est égal, même les nombres n'ont aucun effet, le nombre impair de chiffres (c'est-à-dire un nombre impair de chiffres impairs le rend impair).

Selon la langue, il peut y avoir un moyen plus rapide d'effectuer le calcul sans l'ajouter.

Rappelez-vous aussi qu'un nombre est impair ou même basé sur son dernier chiffre binaire.

Exemple:

En ASM, vous pouvez XOR le bit de poids faible pour obtenir le résultat correct

Forth ce ne serait pas si bien travailler ...