Tous les défis
Facile 2 résolus 66.7 % de réussite

Nombre manquant

Trouvez le nombre manquant dans 0..n.

Ce que vous allez apprendre

  • Calculer la somme attendue de 0..n
  • Trouver la valeur manquante par différence
  • Résoudre en un passage sans trier

Problème

La liste contient n nombres distincts choisis parmi 0, 1, …, n, donc exactement un nombre de cet intervalle est absent. Trouvez-le. (Indice : comparez la somme attendue avec la somme réelle.)

Implémentez missing_number(numbers).

Entrée

numbers : n nombres distincts de 0 à n.

Sortie

Retournez le nombre manquant.

Contraintes

0 ≤ n ≤ 100 000

Exemples

Exemple 1
Entrée :
numbers = [3, 0, 1]

Sortie attendue :
expected = 2
Entrée :
std::vector<long long> numbers = {3, 0, 1};

Sortie attendue :
long long expected = 2;
Entrée :
long[] numbers = new long[] {3, 0, 1};

Sortie attendue :
long expected = 2;

Explication

n = 3, donc l'intervalle est 0–3 ; 2 est manquant.

Exemple 2
Entrée :
numbers = [0]

Sortie attendue :
expected = 1
Entrée :
std::vector<long long> numbers = {0};

Sortie attendue :
long long expected = 1;
Entrée :
long[] numbers = new long[] {0};

Sortie attendue :
long expected = 1;

Explication

n = 1 et l'intervalle est 0–1 ; 1 est manquant.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Les nombres doivent couvrir toute la plage de 0 à n, sauf un trou.

Indice 2

Comparez le total qu’aurait la plage complète avec ce que la liste totalise réellement.

Indice 3

Faites attention au cas où la valeur manquante est 0 ou n.

Complexité attendue

temps O(n), espace supplémentaire O(1)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 HJhettory Jurash Python 784 ms - 4/5 Voir le code
2 KKKaneki Ken Python 874 ms - 3/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 2 solutions complètes ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.