Come trovare il numero mancante in un dato array di numeri interi da 1 a 100

Per rendere il problema interessante, supponiamo che l'array sia in ordine casuale e si suppone che contenga i valori da 1 a 100. Uno di essi manca e viene sostituito o da un duplicato o da un numero non compreso nell'intervallo da 1 a 100.

Un umano potrebbe preparare una tabella con voci da 1 a 100 e poi fare un singolo passaggio attraverso l'array di input e spuntare ogni numero trovato. Poi, un singolo passaggio attraverso il foglio di spunta scoprirebbe quale numero non è stato spuntato.

In termini informatici, questa idea è chiamata "counting sort" e funziona in tempo O(n), prendendo un singolo passaggio attraverso i dati. Funziona solo quando il numero di possibili valori diversi è piccolo.

Si potrebbe essere sorpresi che ci sia un algoritmo di ordinamento che gira più veloce di O(n log n) e che è molto semplice da spiegare, ma l'idea di n log n si applica solo agli ordinamenti che fanno confronti tra elementi.

Se c'è una restrizione a non usare alcuna struttura dati ausiliaria (come il foglio di controllo) allora per qualcosa con solo 100 elementi, non c'è niente di sbagliato nell'ovvio algoritmo O(n^2) di iniziare semplicemente con 1 e cercare l'intero array di input per vedere se è lì. Questo richiede 10.000 ricerche, ma dovrebbe comunque essere eseguito in meno di 1 millisecondo o giù di lì, quindi a chi importa?

Aggiornamento:

Questo sarebbe un problema più interessante se si volesse sapere quale elemento manca o è duplicato in una tabella di 100 milioni di voci. In quel tipo di caso l'ordinamento di conteggio è goffamente grande. Puoi usare una serie di passaggi con un filtro Bloom per trovarlo abbastanza velocemente però. O anche una serie di contatori per i residui di diversi numeri primi... Un sacco di possibilità.