Trouver le nombre manquant dans un tableau : la solution de l'énigme
Question d'entretien pour développeur, sur l'algorithmique et la complexité.
Énoncé
Un tableau contient les entiers de 1 à n, sauf un, et ses éléments sont dans le désordre. Vous connaissez la valeur de n, mais ni le nombre manquant ni l'ordre des éléments. Comment trouver le nombre manquant le plus efficacement possible ?
Un indice ?
Pensez à une propriété arithmétique de la suite des entiers de 1 à n qui permette de retrouver l'élément absent sans le chercher.
Voir la réponse et la solution
Réponse : Soustraire la somme des éléments du tableau à la somme attendue n(n+1)/2 : la différence est le nombre manquant, en O(n) en temps et O(1) en mémoire.
Le raisonnement
La somme des entiers de 1 à n vaut n(n+1)/2, formule qu'il suffit de calculer une seule fois. Si l'on additionne tous les éléments présents dans le tableau, il manque exactement le nombre absent, donc la somme réelle est inférieure à la somme attendue exactement de ce nombre. La différence entre les deux sommes donne directement la valeur recherchée. Le calcul ne parcourt le tableau qu'une seule fois, la complexité est donc en O(n) en temps, et seules quelques variables sont nécessaires, soit O(1) en mémoire supplémentaire. Une autre méthode, tout aussi efficace, consiste à faire le OU exclusif de tous les nombres présents avec ceux de 1 à n : le résultat est le nombre manquant.
Et pour continuer ?
Un bon raisonnement se travaille comme la mémoire : en s'y essayant souvent. Testez-vous ensuite sur nos quiz de culture générale.