O(n) algorithm, find the missing integer

1. Sum the array.
2. Calculate the expected sum using arithmetic progression formula

Given these values: one is 0 + 1 + 2 + ... + n-1, the other is the sum of your actual elements - think how they differ from each other, what does one have that the other does not. Make sure you know it, and the answer is trivial.

EDIT: (Theoretical comment):
Note that sum(array) needs 2*log_2(max(arr)) bits. So, if your elements are all 32 bits integers, you are going to need at most 64 bits to represent the sum.
From purely theoretical approach - it is NOT O(1). However, you can use the array itself (It contains more then 2*log_2(max(arr)) bits) to store the sum.

Use an additional tmp variable initialized with -1, then kind of sort the array in place using tmp as position n :

function find_missing(array)
begin
  tmp := -1
  i := 0;
  while i<length(array)
    if (array[i] = -1) or (array[i] = i) then
      // either on a cell with the right number or 
      // a candiate for the missing number, just go on
      i := i + 1
    else if array[i] = n then
      // use tmp as the nth cell
      array[i]=tmp
      tmp=n
    else
      // swap the value of the current cell with the value
      // of the cell were the value i should be
      swap(array, i, array[i])
    end if
  end while
end

-1 should point to the missing number.

Here goes another approach:

1. Set a temporary variable Number with 0
2. For each element in array, set Number = Number XOR element
3. For each number M, M > N and M < 2**(ceil(log2(N)) set Number = Number XOR M
4. Missing number is Number