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
Input:
numbers = [3, 0, 1]
Output atteso:
expected = 2Input:
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.
Input:
numbers = [0]
Output atteso:
expected = 1Input:
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.