Steps to Reduce a Number to Zero

Q: Quelle est la complexité temporelle de la réduction d’un nombre à zéro ?

L’exécution du processus prend un temps de O(log n) , car au moins toutes les deux étapes, le nombre est divisé par deux. Pour n = 2^31 - 1 , cela représente 61 étapes. Le comptage des chiffres binaires à l’aide d’instructions binaires intégrées est en O(1) .

Q: Quelle est la formule pour le nombre d’étapes ?

Pour n > 0 , la réponse est la longueur de n en binaire, moins un, plus le nombre de bits à 1. Chaque bit à 1 coûte une soustraction et chaque chiffre après le premier 1 coûte une division par deux. Pour n = 0 , la réponse est 0 .

Q: Quel nombre inférieur à 2^31 nécessite le plus d’étapes ?

2^31 - 1 , qui correspond à trente et un 1 en binaire. Il faut 31 soustractions et 30 divisions par deux, soit 61 étapes au total. Aucun nombre plus petit n’a autant de chiffres et autant de 1 à la fois.

DébutantManipulation de bits Maths et simulation

+10

Partez d’un entier non négatif n et répétez une règle jusqu’à ce qu’il atteigne 0 : si le nombre est pair, divisez-le par 2 ; s’il est impair, soustrayez 1. Chaque application de la règle compte pour une étape. Renvoyez le nombre d’étapes nécessaires.

Fonction

numberOfSteps(n: integer) → integer

ninteger: le nombre de départ
Renvoieinteger: le nombre d’étapes jusqu’à ce que le nombre atteigne 0

Contraintes

0 ≤ n ≤ 2³¹ - 1

Exemples

Entrée: n = 14
Sortie: 6
Explication: Le nombre suit la séquence 14 → 7 → 6 → 3 → 2 → 1 → 0 : trois divisions par deux et trois soustractions, 6 étapes.

Entrée: n = 8
Sortie: 4
Explication: 8 → 4 → 2 → 1 → 0. Une puissance de deux est divisée par deux trois fois et nécessite une soustraction à la fin, 4 étapes.

Entrée: n = 123
Sortie: 12
Explication: 123 est 1111011 en binaire : sept chiffres et six 1. Les six 1 nécessitent six soustractions et les six chiffres sous le 1 de tête nécessitent six divisions par deux, soit 12 étapes.

+12 tests cachés à la soumission

Pour aller plus loin

Supposons qu’un nombre impair puisse aussi augmenter de 1 au lieu de diminuer. Quel est le nombre minimal d’étapes pour atteindre 0, et quel choix est le bon pour 15 ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Exécuter la règle est déjà rapide : chaque division par deux réduit le nombre de moitié, donc même 2^31 - 1 ne nécessite que 61 étapes. Ce qui est intéressant, c’est de voir ce que la règle fait aux chiffres binaires. La division par deux supprime le dernier chiffre, et la soustraction de 1 à un nombre impair transforme son dernier 1 en 0. La réponse est donc le nombre de chiffres plus le nombre de 1, moins un.

Exécuter le processus

Intuition

Faites ce que l’instruction indique. Tant que n est supérieur à 0, divisez-le par deux s’il est pair, soustrayez 1 s’il est impair et comptez l’étape. Pour 14, la boucle passe par 7, 6, 3, 2, 1 et 0, soit six étapes.

La boucle est courte parce qu’une soustraction rend toujours un nombre impair pair, donc au moins une étape sur deux est une division par deux. Un nombre inférieur à 2^31 est divisé par deux au plus 30 fois avant d’atteindre 1 et, avec une soustraction avant chaque division par deux et une à la fin, la boucle s’exécute au plus 61 fois.

L’entrée 0 ne nécessite aucun cas particulier : la condition de la boucle est immédiatement fausse et la réponse est 0.

Algorithme

Définis steps à 0.
Tant que n > 0 : si n est pair, définis n à n / 2, sinon à n-1.
Ajoute 1 à steps à chaque fois.
Retourne steps.

def numberOfSteps(n):
    steps = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps

Comptez les chiffres binaires

Intuition

Observez le processus en binaire. 14 est 1110. La division par deux supprime le dernier chiffre : 111. Soustraire 1 à un nombre impair efface son dernier chiffre, un 1 : 110. Ainsi, à chaque étape, on supprime le dernier chiffre ou on transforme un 1 final en 0.

Maintenant, comptons. Chaque 1 du nombre doit être effacé une fois, ce qui coûte une soustraction par 1. Chaque chiffre doit être supprimé, ce qui coûte une division par deux par chiffre, à l’exception du premier : lorsqu’il ne reste que 1, la soustraction qui l’efface donne déjà 0. La réponse est donc length - 1 + ones. Pour 14 = 1110, cela donne 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust et Swift disposent de fonctions intégrées pour ces deux comptages (le nombre de zéros en tête et le nombre de bits à 1), qui se compilent en instructions uniques sur la plupart des processeurs. Dans les autres langages, on écrit n en binaire et on compte les caractères, ou on lit les chiffres avec % 2 ; cela correspond à une boucle d’au plus 31 itérations. Renvoyez d’abord 0 pour n = 0 : il ne contient aucun bit à 1 pour servir de point d’ancrage à la formule.

Algorithme

Si n == 0, renvoie 0.
Détermine length, le nombre de chiffres binaires de n.
Détermine ones, le nombre de bits à 1.
Renvoie length - 1 + ones.

def numberOfSteps(n):
    if n == 0:
        return 0
    # Every bit below the leading one costs a halving,
    # and every 1 bit costs a subtraction.
    return n.bit_length() - 1 + bin(n).count("1")

Pièges et cas limites

La règle tient en deux lignes. Les erreurs se trouvent dans les cas limites et dans le décalage de la formule d'une unité.

Oublier n = 0 dans la formule des bits. Sans chiffres et sans 1, length - 1 + ones donne -1, et le nombre de zéros en tête, égal à 0, peut être indéfini (__builtin_clz(0) en C).
Compter une division par deux pour le chiffre de tête. 1 devient 0 par une soustraction, donc 8 = 1000 nécessite 4 - 1 + 1 = 4 étapes, et non 5.
Fusionner deux étapes en une. Écrire n = (n-1) / 2 pour un nombre impair effectue une soustraction et une division par deux à la fois : il faut donc ajouter 2 au compteur, et non 1. Sinon, 14 donne 4 au lieu de 6.
Répéter la boucle tant que n > 1. Elle s'arrête une étape trop tôt, car la dernière étape transforme 1 en 0. La boucle doit s'exécuter jusqu'à ce que n soit égal à 0.

Questions fréquentes4

Quelle est la complexité temporelle de la réduction d’un nombre à zéro ?

L’exécution du processus prend un temps de O(log n), car au moins toutes les deux étapes, le nombre est divisé par deux. Pour n = 2^31 - 1, cela représente 61 étapes. Le comptage des chiffres binaires à l’aide d’instructions binaires intégrées est en O(1).

Quelle est la formule pour le nombre d’étapes ?

Pour n > 0, la réponse est la longueur de n en binaire, moins un, plus le nombre de bits à 1. Chaque bit à 1 coûte une soustraction et chaque chiffre après le premier 1 coûte une division par deux. Pour n = 0, la réponse est 0.

Quel nombre inférieur à 2^31 nécessite le plus d’étapes ?

2^31 - 1, qui correspond à trente et un 1 en binaire. Il faut 31 soustractions et 30 divisions par deux, soit 61 étapes au total. Aucun nombre plus petit n’a autant de chiffres et autant de 1 à la fois.

Pourquoi diviser par deux revient-il à effectuer un décalage vers la droite ?

Un nombre binaire est une somme de puissances de deux. Diviser un nombre pair par 2 réduit chaque puissance de un, ce qui déplace chaque chiffre d’une position vers la droite et supprime le 0 final. C’est exactement ce que fait n >> 1, tu peux donc écrire la division par deux de l’une ou l’autre façon.

Python

def numberOfSteps(n):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

n = 14

Attendu