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 O(log n) , car au moins une étape sur deux divise le nombre par deux : 61 étapes pour n = 2^31 - 1 . Compter les chiffres binaires avec des instructions binaires intégrées est en O(1) .

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

2^31 - 1 , soit 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 correspond à 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, soit 4 étapes.

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

Pour aller plus loin

Supposons qu’un nombre impair puisse également augmenter de 1. Quel est le nombre minimal d’étapes pour atteindre 0, et quel choix est correct pour 15 ?

Indices

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

0 sur 3 ouverts

Solution

En binaire, diviser par deux supprime le dernier chiffre, et soustraire 1 à un nombre impair transforme son dernier 1 en 0. Donc, pour n > 0, la réponse est le nombre de chiffres binaires plus le nombre de 1, moins un. Appliquer directement la règle est également rapide : au plus 61 étapes.

Exécute le processus

Intuition

Applique la règle et compte les étapes. Pour 14, la boucle visite 7, 6, 3, 2, 1 et 0 : six étapes.

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 maximum 30 fois avant d’atteindre 1. Avec une soustraction avant chaque division par deux et une à la fin, la boucle s’exécute au maximum 61 fois. Pour n = 0, la boucle ne s’exécute jamais 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

Compter les chiffres binaires

Intuition

Chaque étape supprime le dernier chiffre binaire ou transforme un 1 final en 0. 14 s’écrit 1110 : la division par deux donne 111, et la soustraction à partir de 111 donne 110. Chaque 1 doit être effacé une fois, ce qui coûte une soustraction par 1. Chaque chiffre doit être supprimé, une division par deux à la fois, sauf le premier : lorsqu’il ne reste que 1, sa soustraction donne déjà 0. La réponse est donc length - 1 + ones, et pour 14, cela donne 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust et Swift disposent de fonctions intégrées pour les deux comptages (les zéros en tête et les bits à 1) qui se compilent en une seule instruction sur la plupart des processeurs. Les autres langages lisent les chiffres avec % 2 dans une boucle d’au plus 31 tours. Traitez d’abord n = 0 : il ne contient aucun bit à 1 pour ancrer la formule.

Algorithme

Si n == 0, renvoie 0.
Trouve length, le nombre de chiffres binaires de n.
Trouve 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

Oublier n = 0 dans la formule des bits. length - 1 + ones donne -1, et le nombre de zéros de tête peut être indéfini pour 0 (__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.
Écrire n = (n-1) / 2 pour un nombre impair et compter une étape. Cette ligne effectue deux étapes, donc 14 donne 4 au lieu de 6.
Faire une boucle tant que n > 1. Elle s'arrête avant la dernière étape, qui transforme 1 en 0.

Questions fréquentes3

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

L’exécution du processus prend un temps O(log n), car au moins une étape sur deux divise le nombre par deux : 61 étapes pour n = 2^31 - 1. Compter les chiffres binaires avec des instructions binaires intégrées est en O(1).

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

2^31 - 1, soit 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 abaisse chaque puissance d’une unité, ce qui décale chaque chiffre d’une place vers la droite et supprime le 0 final. C’est ce que fait n >> 1, donc tu peux écrire la division par deux de l’une ou l’autre manière.

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

Test #1

Test #2

Test #3

Argument

n = 14

Résultat attendu