Tutte le sfide
Facile 2 risolte 66.7% di accettazione

Numero Mancante

Trova l'unico numero mancante da 0 a n.

Cosa imparerai

  • Calcolare la somma attesa di 0..n
  • Trovare il valore mancante dalla differenza
  • Risolvere in un passaggio senza ordinare

Problema

La lista contiene n numeri distinti presi da 0, 1, …, n, quindi manca esattamente un numero in quell'intervallo. Trovalo. (Suggerimento: confronta il totale atteso con il totale effettivo.)

Implementa missing_number(numbers).

Input

numbers: n numeri distinti da 0 a n.

Output

Restituisci il numero mancante.

Vincoli

0 ≤ n ≤ 100.000

Esempi

Esempio 1
Input:
numbers = [3, 0, 1]

Output atteso:
expected = 2
Input:
std::vector<long long> numbers = {3, 0, 1};

Output atteso:
long long expected = 2;
Input:
long[] numbers = new long[] {3, 0, 1};

Output atteso:
long expected = 2;

Spiegazione

n = 3, quindi l'intervallo è 0–3; manca il 2.

Esempio 2
Input:
numbers = [0]

Output atteso:
expected = 1
Input:
std::vector<long long> numbers = {0};

Output atteso:
long long expected = 1;
Input:
long[] numbers = new long[] {0};

Output atteso:
long expected = 1;

Spiegazione

n = 1 e l'intervallo è 0–1; manca l'1.

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

I numeri dovrebbero coprire l'intervallo completo da 0 a n, tranne un buco.

Suggerimento 2

Confronta il totale dell'intervallo completo con quello effettivo della lista.

Suggerimento 3

Fai attenzione al caso in cui il valore mancante sia 0 o n.

Complessità attesa

tempo O(n), spazio aggiuntivo O(1)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

# Programmatore Linguaggio Tempo Memoria Voto dell'IA Soluzione
1 HJhettory Jurash Python 784 ms - 4/5 Vedi il codice
2 KKKaneki Ken Python 874 ms - 3/5 Vedi il codice

Impara dagli altri

Soluzioni della community

Attenzione spoiler: 2 soluzioni complete sotto Prova prima a risolverla da solo. Puoi comunque sbirciare il codice degli altri sviluppatori e le recensioni AI. Accedi e risolvi la sfida per partecipare alla discussione.