Finding missing numbers in an array

Question

Given an array of size n, which contains numbers in the range 1 to n, and in which each number is present at least once, but some numbers may be missing, how can I find the missing numbers?

Answer 1

for i in 1..n
  if !array.contains(i)
    missing.add(i)

Answer 2

Use an additional array of size n, and leverage its indexes by correlating them to numbers.

Answer 3

I'll assume that the array's length is O(n).

Carl Manaster gives an approach that should run in O(n²) and uses O(1) additional memory. But you can trade time for space:

contains = [false]*(n+1)
for i in array
    contains[i] = true

for i in 1..n
    if !contains[i]
        yield i

That is O(n) memory and space. You can also get O(n log n) time and O(1) space however:

array.add(0, n+1)
array.sort()
for i in 0..array.length-2
    for j in array[i]+1..array[i+1]-1
        yield j

This algorithm first sorts the values. It then find the gaps between values and yields the values. Assuming a good sorting algorithm this can run in O(n log n) time and O(1) additional space. If the array is already sorted this is the way to do it!

Answer 4

The quick answer: XOR

Space complexity O(1), time complexity O(n).

See below sample C# code:

int[] i = { 1, 3, 4 };
int z = 4;

foreach (int s in i)
    z = z ^ s;

Console.WriteLine(z);   // Print 2

int[] j = { 1, 2, 3, 4 };
int y = 4;

foreach (int s in j)
    y = y ^ s;

Console.WriteLine(y);   // Print 0

int[] k = { 1, 2, 4 };
int x = 4;

foreach (int s in k)
    x = x ^ s;

Console.WriteLine(x);   // Print 3

Answer 5

If it's an unsorted array and more than one number can be missing in a sequence starting from 1 to a specified length n, O(n) time and space algo is to use hashing...

Pass through the input array once and hash them. Then, pass through 1 to n and yield anything that's not hashed.