Missing Number

FacileManipulation de bits Maths et simulation

+10

On te donne une liste nums de n entiers distincts, chacun compris entre 0 et n. L’intervalle de 0 à n contient n+1 nombres, donc exactement un d’entre eux ne figure pas dans la liste. Retourne ce nombre manquant.

Fonction

missingNumber(nums: integer-array) → integer

numsinteger-array: n entiers distincts compris entre 0 et n, dans n’importe quel ordre
Renvoieinteger: l’unique nombre de 0 à n qui ne figure pas dans nums

Contraintes

n == nums.length
1 ≤ n ≤ 10⁴
0 ≤ nums[i] ≤ n
Toutes les valeurs de nums sont distinctes.

Exemples

Entrée: nums = [4, 2, 0, 1]
Sortie: 3
Explication: La liste contient 4 valeurs, donc la plage va de 0 à 4. Elle contient 0, 1, 2 et 4, et 3 est le seul nombre sans correspondance.

Pour aller plus loin

Si la liste était triée, pourrais-tu trouver le nombre manquant en O(log n) avec une recherche binaire ?

Indices

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

0 sur 3 ouverts

Solution

Tu sais exactement ce que la liste doit contenir : chaque entier de 0 à n. Rechercher chacun de ces nombres un par un fonctionne, mais répète un parcours complet pour chaque nombre. À la place, résume toute la plage et la liste par une seule valeur chacune, leur somme ou leur XOR, et la différence entre les deux donne le nombre manquant. Cela ne nécessite qu’un seul parcours et aucune mémoire supplémentaire.

Vérifiez chaque candidat

Correcte, mais ne termine pas sur les plus gros tests

Intuition

La réponse est l’un des n+1 nombres de 0 à n. Prenez-les dans l’ordre et parcourez la liste à la recherche de chacun d’eux. Le premier candidat introuvable dans la liste est le nombre manquant.

C’est correct, car chaque nombre de l’intervalle se trouve soit dans la liste, soit correspond à la réponse, et la liste ne contient aucun doublon. Ainsi, exactement un candidat ne sera pas trouvé.

Cette méthode est lente, car chaque candidat nécessite de parcourir jusqu’à n valeurs. Lorsque l’écart se situe près de la fin, presque tous les candidats sont recherchés : avec n = 10^4 et l’écart près de la fin, cela représente environ 5 × 10^7 comparaisons. Doubler la taille de la liste quadruple le travail.

Algorithme

Parcourez les valeurs de candidate de 0 à n inclus.
Parcourez nums à la recherche d’une valeur égale à candidate.
Si le parcours la trouve, passez à la valeur candidate suivante.
Si le parcours se termine sans correspondance, renvoyez candidate.

def missingNumber(nums):
    n = len(nums)
    for candidate in range(n + 1):
        # "in" on a list scans it from the start: O(n) per candidate.
        if candidate not in nums:
            return candidate
    return -1

Soustrayez la somme de la somme attendue

Intuition

S'il ne manquait aucun nombre, la liste contiendrait tous les nombres de 0 à n, dont la somme est égale à n(n+1)/2. La vraie liste est cet ensemble complet auquel il manque un nombre ; sa somme est donc inférieure exactement de ce nombre.

Pour [4, 2, 0, 1], n vaut 4 et la somme de la plage complète est égale à 4 × 5 / 2 = 10. La somme de la liste est 7, et 10 moins 7 donne 3.

Un seul passage suffit pour additionner les éléments de la liste : le temps d'exécution est donc O(n), et tu conserves un seul total courant. Ici, la somme complète est d'environ 5 × 10^7 au maximum, ce qui tient dans un entier de 32 bits. Pour des valeurs de n beaucoup plus grandes, la formule dépasse la capacité d'un int de 32 bits ; les versions Java, C, C++, C# et Rust effectuent donc le calcul sur 64 bits.

Algorithme

Soit n la longueur de nums.
Calculez la somme complète n(n+1)/2.
Additionnez toutes les valeurs de nums.
Retournez la somme complète moins la somme de la liste.

def missingNumber(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

Effectuer un XOR entre les indices et les valeurs

Intuition

XOR annule les paires. a ^ a vaut 0, a ^ 0 vaut a, et l’ordre des opérations n’a pas d’importance. Ainsi, si tu appliques XOR à un ensemble de nombres où tout apparaît deux fois sauf une valeur, les paires s’annulent et cette valeur est celle qui reste.

Construis un tel ensemble à partir du problème : les indices de 0 à n, plus les valeurs de nums. Un nombre présent dans la liste apparaît une fois comme indice et une fois comme valeur, donc il s’annule. Le nombre manquant apparaît uniquement comme indice, donc il reste. La boucle parcourt les indices de 0 à n-1, alors initialise le résultat à n pour inclure le dernier.

Pour [4, 2, 0, 1] : commence à 4, puis applique XOR à 0 et 4, 1 et 2, 2 et 0, 3 et 1. Les 4, les 2, les 1 et les 0 s’annulent tous, et il reste 3. Cela se fait en un seul parcours avec une seule valeur courante et, contrairement à la somme, cette valeur ne dépasse jamais les bits déjà utilisés par n, donc elle ne peut pas déborder.

Algorithme

Définissez result sur n, la longueur de nums.
Pour chaque indice i, effectuez un XOR entre result, i et nums[i].
Retournez result.

def missingNumber(nums):
    # Start with n, the one index the loop below never reaches.
    result = len(nums)
    for i, value in enumerate(nums):
        result ^= i ^ value
    return result

Pièges et cas limites

La plupart des mauvaises réponses viennent des deux extrémités de l’intervalle.

Oublier que n lui-même peut être manquant. Dans [0, 1, 2], la réponse est 3, qui n’est pas un indice de la liste. La version avec XOR doit commencer à n, et un parcours trié qui recherche le premier nums[i] != i doit renvoyer n lorsque toutes les positions correspondent.
Utiliser une taille d’intervalle incorrecte. Les nombres vont de 0 à n, soit n+1 nombres, donc la somme totale est n(n+1)/2, et non (n-1)n/2.
Supposer que 0 est toujours présent. Dans [1], la réponse est 0, et le code qui commence sa recherche à 1 ne le trouve pas.
Débordement dans la version avec la somme. En arithmétique sur 32 bits, le produit n(n+1) déborde dès que n dépasse environ 46 000, avant que la division par 2 puisse aider, et n(n+1)/2 lui-même cesse de tenir vers 65 000. Utilisez l’arithmétique sur 64 bits, ou XOR.

Questions fréquentes3

Quelle est la complexité temporelle de Missing Number ?

Les solutions par somme et par XOR s’exécutent toutes deux en O(n) et utilisent O(1) d’espace supplémentaire, puisqu’elles lisent chaque valeur une seule fois et ne conservent qu’un nombre. Parcourir la liste pour chaque candidat prend O(n²). Trier d’abord la liste puis chercher l’écart prend O(n log n).

Pourquoi XOR permet-il de trouver le nombre manquant ?

Faire un XOR d’un nombre avec lui-même donne 0, faire un XOR avec 0 ne change rien, et l’ordre n’a pas d’importance. Lorsque vous faites un XOR de tous les indices de 0 à n ainsi que de toutes les valeurs, chaque nombre présent dans la liste apparaît deux fois et s’annule. Le nombre manquant n’apparaît qu’une seule fois, en tant qu’indice, c’est donc le résultat.

Faut-il utiliser la formule de la somme ou XOR ?

Les deux nécessitent un seul passage et une mémoire constante. La somme est plus facile à expliquer, mais en arithmétique sur 32 bits, le produit n(n+1) déborde dès que n dépasse environ 46 000 ; il faut donc utiliser l’arithmétique sur 64 bits. XOR ne déborde jamais. En Python, Ruby et dans les autres langages à entiers de taille illimitée, cette différence disparaît.

def missingNumber(nums):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

nums = [4, 2, 0, 1]

Résultat attendu

Missing Number

Fonction

Contraintes

Exemples

Indices

Solution

Vérifiez chaque candidat

Soustrayez la somme de la somme attendue

Effectuer un XOR entre les indices et les valeurs

Pièges et cas limites

Questions fréquentes3

Problèmes similaires