O(n) algorithm, find the missing integer

Question

An array A contains n-1 unique integers in the range [0, n-1], that is, there is one number from this range that is not in A. Design an O(n) algorithm for finding that number. Allowed to use only O(1) additional space besides the array A itself.

need some help for this question,

• Raymond Chen: possible duplicate of What's the optimal way to calculate which integer in a list is missing?

Answer 1

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.

• codeling: awww, come on man, why did you give the correct answer right away, that's far to easy, let the OP think for him-/herself a bit ;)
• amit: @nyarlathotep: Advise taken, I editted the answer to be more hinting then answering.
• codeling: yep, nice edit :D. could be homework after all, we don't want to make that too easy ;)
• chepner: This uses O(lg n) additional space, as the space necessary for the sum is not independent of n.
• amit: @chepner I Disagree. You can use the array itself (it is not counted as additional). Assuming we use some fixed integer size to represent elements (so all elements in the array take the same number of bits), the 2 first elements are enough to sum the array, leaving us with O(1) additional space. (Without this assumption we can fit it too, but we might need more elements).

Answer 2

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.

Answer 3

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