
Manglende tal. Lad A være et array af længde n − 1 således at indgangene i A er tal i mængden
{0, 1, 2, . . . , n − 1}, hvor det oplyses at alle indgangene er forskellige. Derfor er der alts å et enkelt tal
i mængden {0, 1, . . . , n − 1} som ikke optræder i A, og dette kalder vi det manglende tal.
F.eks. med n = 5 og A = [2, 0, 4, 3] er det manglende tal m = 1.
Vi er interesserede i effektive algoritmer til at finde det manglende tal i A. Løs følgende opgaver.

a) Giv en algoritme der løser problemet i Θ(n) tid. Hint: Brug et ekstra array af længde n.

