Plus One

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

Les deux approches s’exécutent en temps O(n) pour n chiffres, car le pire cas, celui où tous les chiffres sont des 9, parcourt chaque chiffre. La version avec arrêt anticipé s’arrête après les 9 finaux ; pour un nombre qui se termine par un chiffre inférieur à 9, elle effectue donc une seule étape. Elle 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 nombre entier non négatif est stocké sous forme de tableau de ses chiffres décimaux, digits, du chiffre le plus significatif au moins significatif : 472 correspond à [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 n’a pas de zéro initial, 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.

+13 tests cachés à la soumission

Pour aller plus loin

Comment soustrairais-tu plutôt un, pour un nombre d’au moins 1 ? Quels chiffres changent, et quand le résultat perd-il son chiffre de tête, comme dans [1, 0, 0] ?

Solution

Convertir les chiffres en nombre, ajouter un puis reconvertir échoue ici : 100 chiffres dépassent la capacité de tout entier sur 64 bits, qui s’arrête aux environs de 1.8 × 10^19. Il faut donc additionner comme on le fait sur papier, en partant du dernier chiffre et en reportant la retenue. La seule observation qui réduit le travail : ajouter 1 ne change que les 9 finaux, qui deviennent des 0, ainsi que le premier chiffre à leur gauche. Tous les autres chiffres restent inchangés.

Addition avec retenue, chiffre par chiffre

Intuition

Écrivez le nombre et ajoutez 1 sous son dernier chiffre, comme à l’école. 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. Son dernier chiffre, total % 10, est placé dans la réponse, et son chiffre des dizaines, total / 10, devient la retenue pour la colonne suivante.

Avec une retenue de 1, le total d’une colonne est au plus égal à 9 + 1 = 10 ; la retenue vaut donc toujours 0 ou 1. S’il reste une retenue après le premier chiffre, la réponse gagne un nouveau chiffre en tête : 999 + 1 nécessite une quatrième position pour le 1 de 1000.

La réponse est produite en commençant par le dernier chiffre, car c’est dans cet ordre que vous la calculez. Collectez les chiffres dans cet ordre, puis inversez-les à la fin. Cela coûte O(n) en temps et nécessite un nouveau tableau pouvant contenir jusqu’à n + 1 chiffres.

Algorithme

Définissez carry à 1 et commencez 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-toi au premier chiffre inférieur à 9

Intuition

Observez ce qui arrive à la retenue lorsque vous ajoutez exactement 1. Un chiffre inférieur à 9 l’absorbe : 3 devient 4, la retenue devient 0 et tous les chiffres situés plus à gauche conservent leur valeur. Seul un 9 transmet la retenue en devenant 0. Ajouter 1 revient donc à transformer les 9 consécutifs à la fin en 0, puis à ajouter 1 au chiffre qui les précède.

Parcourez les chiffres de droite à gauche. Pour un 9, écrivez 0 et continuez. Pour tout autre chiffre, augmentez-le de un et renvoyez immédiatement le tableau, puisque rien à sa gauche ne peut changer. Pour [2, 9, 0, 9], le dernier 9 devient 0, le 0 devient 1, et vous vous arrêtez avec [2, 9, 1, 0] sans examiner les deux premiers chiffres.

Si la boucle ne trouve jamais de chiffre inférieur à 9, tous les chiffres étaient des 9 et sont maintenant des 0. Le nombre était 10^n - 1, donc la réponse est un 1 suivi de n zéros. C’est le seul cas qui nécessite un nouveau tableau. Dans tous les autres cas, vous modifiez l’entrée sur place, donc l’espace supplémentaire est O(1), et la boucle s’exécute une fois par 9 final, plus une étape supplémentaire.

Algorithme

Parcourez les indices du dernier au premier.
Si le chiffre est inférieur à 9, augmentez-le de 1 et renvoyez le tableau.
Sinon, le chiffre vaut 9 : définissez-le sur 0 et déplacez-vous d’une place vers la gauche.
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

Les pièges sont le dépassement de capacité des entiers et le cas où tous les chiffres sont des 9.

Convertir le tableau en entier, puis le reconvertir. Cela fonctionne pour les petits tests, puis échoue avec les nombres de 100 chiffres : un entier de 64 bits peut contenir au plus 19 ou 20 chiffres, et un nombre à virgule flottante perd les derniers chiffres encore plus tôt.
Oublier le chiffre supplémentaire. [9, 9, 9] doit devenir [1, 0, 0, 0], soit quatre chiffres. Le code qui ne modifie que les positions existantes renvoie [0, 0, 0].
Ajouter 1 au premier chiffre au lieu du dernier. Le tableau est ordonné du chiffre le plus significatif au moins significatif, donc le chiffre des unités se trouve à la fin.
Oublier de renvoyer le résultat lorsqu’un chiffre inférieur à 9 absorbe la retenue. Dans la version avec sortie anticipée, la boucle continue et modifie des chiffres qui doivent rester tels quels. Dans [1, 9, 3], seul le 3 peut changer ; la réponse est [1, 9, 4].
Confondre l’ordre des indices en Lua et en R, où les tableaux commencent à l’indice 1 : le dernier chiffre se trouve à l’indice n, et un nouveau 1 en tête se place avant l’indice 1.

Questions fréquentes4

Quelle est la complexité temporelle de Plus One ?

Les deux approches s’exécutent en temps O(n) pour n chiffres, car le pire cas, celui où tous les chiffres sont des 9, parcourt chaque chiffre. La version avec arrêt anticipé s’arrête après les 9 finaux ; pour un nombre qui se termine par un chiffre inférieur à 9, elle effectue donc une seule étape. Elle 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 ?

Comme le nombre peut avoir 100 chiffres et qu’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 elle masque l’objectif de l’exercice et ne se transpose pas à d’autres langages. Traiter les chiffres un par un ne provoque jamais de dépassement de capacité.

Quand le résultat comporte-t-il plus de chiffres que l’entrée ?

Uniquement lorsque chaque chiffre est égal à 9. Le nombre est alors 10^n - 1, et ajouter un donne 10^n : un 1 suivi de n zéros. Si un chiffre est inférieur à 9, il absorbe la retenue, donc la longueur reste la même.

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

Utilisez la méthode par colonnes de la première approche avec deux indices, un à la fin de chaque tableau. Chaque colonne additionne les deux chiffres, en considérant qu’un chiffre manquant vaut 0, ainsi que la retenue. Continuez jusqu’à ce que les deux tableaux soient épuisés et que la retenue soit égale à 0, puis inversez les chiffres recueillis.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

digits = [4, 3, 9]

Attendu

[4, 4, 0]