Plus One

Q: Quelle est la complexité temporelle de Plus One ?

Les deux approches s’exécutent en O(n) pour n chiffres, car le cas où tous les chiffres sont des 9 parcourt chaque chiffre. La version avec arrêt anticipé s’arrête après les 9 finaux et utilise un espace supplémentaire de O(1) , sauf lorsque la réponse nécessite un nouveau chiffre en tête.

FacileMaths et simulation

+10

Un entier non négatif est stocké sous forme de tableau de ses chiffres décimaux, digits, le chiffre le plus significatif en premier : 472 est [4, 7, 2]. Ajoutez un au nombre et renvoyez les chiffres du résultat sous la même forme. Le nombre peut comporter jusqu’à 100 chiffres, bien plus qu’un entier de 64 bits ne peut en contenir.

Fonction

plusOne(digits: integer-array) → integer-array

digitsinteger-array: les chiffres du nombre, du plus significatif au moins significatif
Renvoieinteger-array: les chiffres du nombre plus un, du plus significatif au moins significatif

Contraintes

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits ne comporte aucun zéro en tête, sauf pour le nombre 0 lui-même, qui est [0].

Exemples

Entrée: digits = [4, 3, 9]
Sortie: [4, 4, 0]
Explication: Le nombre est 439, et 439 + 1 = 440. Le dernier chiffre 9 devient 0 et transmet une retenue au 3, qui devient 4.

Entrée: digits = [0]
Sortie: [1]
Explication: Le nombre 0 s’écrit [0], et 0 + 1 = 1.

Pour aller plus loin

Comment soustrairais-tu plutôt un, pour un nombre d’au moins 1 ? Dans quel cas le résultat perd-il son chiffre initial, comme dans [1, 0, 0] ?

Solution

Un nombre de 100 chiffres dépasse la capacité de tous les entiers de 64 bits, qui s’arrêtent près de 1.8 × 10^19 ; vous ne pouvez donc pas le convertir puis l’additionner. Additionnez comme vous le feriez sur papier, en partant du dernier chiffre et en reportant la retenue. Ajouter 1 ne modifie que les 9 finaux, qui deviennent des 0, ainsi que le chiffre à leur gauche.

Addition avec retenue, chiffre par chiffre

Intuition

Commencez avec une retenue de 1, celle que vous ajoutez. Pour chaque chiffre en partant de la droite, le total de la colonne est le chiffre plus la retenue : total % 10 entre dans la réponse et total / 10 est la retenue suivante. Un total vaut au plus 9 + 1 = 10, donc la retenue reste égale à 0 ou 1. Une retenue restante après le premier chiffre devient un nouveau chiffre en tête, comme dans 999 + 1 = 1000.

Vous produisez la réponse en commençant par le dernier chiffre ; recueillez-la donc dans cet ordre et inversez-la à la fin. Cela prend un temps de O(n) et nécessite un nouveau tableau de jusqu’à n + 1 chiffres.

Algorithme

Définissez carry à 1 et créez une liste vide pour la réponse.
Pour chaque chiffre, du dernier au premier, calculez total = digit + carry.
Ajoutez total % 10 à la réponse et définissez carry à total / 10, arrondi à l'entier inférieur.
Après la boucle, si carry vaut 1, ajoutez-le.
Inversez la réponse et renvoyez-la.

def plusOne(digits):
    result = []  # the answer, last digit first
    carry = 1  # the one you are adding
    for i in range(len(digits) - 1, -1, -1):
        total = digits[i] + carry
        result.append(total % 10)
        carry = total // 10
    if carry > 0:
        result.append(carry)
    result.reverse()
    return result

Arrête au premier chiffre inférieur à 9

Intuition

Un chiffre inférieur à 9 absorbe une retenue de 1 : il augmente de un et chaque chiffre à sa gauche conserve sa valeur. Seul un 9 transmet la retenue en devenant 0. Tu peux donc t’arrêter au premier chiffre inférieur à 9 et renvoyer le tableau d’entrée, modifié sur place. Pour [2, 9, 0, 9], le dernier 9 devient 0, le 0 devient 1, et tu renvoies [2, 9, 1, 0] sans lire les deux premiers chiffres.

Si aucun chiffre n’est inférieur à 9, le nombre était 10^n - 1 et la réponse est 1 suivi de n zéros. C’est le seul cas qui nécessite un nouveau tableau ; l’espace supplémentaire est donc O(1) dans les autres cas.

Algorithme

Parcourez les indices du dernier au premier.
Si le chiffre est inférieur à 9, augmentez-le de un et renvoyez le tableau.
Sinon, le chiffre vaut 9 : remplacez-le par 0 et passez à la position précédente.
Si la boucle se termine, tous les chiffres étaient des 9 : renvoyez 1 suivi de n zéros.

def plusOne(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1  # no carry leaves this digit, so the rest stays as it is
            return digits
        digits[i] = 0  # 9 + 1 = 10: write 0 and carry one to the left
    # Every digit was 9: the answer is 1 followed by zeros.
    return [1] + digits

Pièges et cas limites

Convertir le tableau en entier, puis de nouveau en tableau. Un entier de 64 bits contient au maximum 19 ou 20 chiffres. Avec 100 chiffres, il y a donc un dépassement de capacité, et un nombre à virgule flottante perd ses derniers chiffres encore plus tôt.
Oublier le chiffre supplémentaire. [9, 9, 9] doit devenir [1, 0, 0, 0] ; le code qui ne réécrit que les positions existantes renvoie [0, 0, 0].
Ajouter 1 au premier chiffre. Le tableau est ordonné du chiffre le plus significatif au moins significatif : le chiffre des unités est donc le dernier élément.
Ne pas s’arrêter lorsqu’un chiffre inférieur à 9 absorbe la retenue. La boucle modifie alors des chiffres qui doivent rester inchangés : [1, 9, 3] doit devenir [1, 9, 4].
En Lua et en R, les tableaux commencent à 1 : le dernier chiffre se trouve donc à l’index n, et non n - 1.

Questions fréquentes3

Quelle est la complexité temporelle de Plus One ?

Les deux approches s’exécutent en O(n) pour n chiffres, car le cas où tous les chiffres sont des 9 parcourt chaque chiffre. La version avec arrêt anticipé s’arrête après les 9 finaux et utilise un espace supplémentaire de O(1), sauf lorsque la réponse nécessite un nouveau chiffre en tête.

Pourquoi ne pas convertir les chiffres en entier ?

Le nombre peut avoir 100 chiffres, et un entier de 64 bits s’arrête à environ 1,8 × 10^19, soit 20 chiffres. Python et Ruby ont des entiers illimités, donc la conversion fonctionne dans ces langages, mais le code n’est pas transposable à d’autres langages. Traiter les chiffres un par un ne provoque jamais de dépassement de capacité.

Comment additionner deux nombres stockés sous forme de tableaux de chiffres ?

Utilisez la méthode par colonnes avec un index à la fin de chaque tableau. Chaque colonne additionne les deux chiffres, en considérant un chiffre manquant comme 0, ainsi que la retenue. Arrêtez-vous lorsque les deux tableaux sont épuisés et que la retenue est égale à 0, puis inversez les chiffres obtenus.

def plusOne(digits):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

digits = [4, 3, 9]

Résultat attendu

[4, 4, 0]