Find "Missing" Integer in a Java Array

Question

Given an array A[] of length n, find a "missing" number k such that:

• k is not in A
• 0<=k<=n

I've seen similar questions asked where the A[] contains numbers 1 to n with one number missing, but in this question, A[] can contain any numbers. I need a solution in O(n) time. For example,

A = {1,2,3} -> 0
A = {0,1,2} -> 3
A = {2,7,4,1,6,0,5,-3} -> 3,8

I've gotten as far as checking if 0 or n are in the array, and if not, return 0 or n, but I cannot seem to think of any other solution. This problem seems considerably more difficult given the fact that A can contain any numbers and not necessarily numbers 1 to n or something like that.

Answer 1

Linearly iterate over the array and "cross out" every number you encounter. Then iterate of that listed of crossed out numbers again and see which one is missing.

 public static int getMissingNumber(int[] A) 
 {  
    int n = A.length;  
    boolean[] numbersUsed = new boolean[n + 1]; //Because the definition says 0 <= k <= n, so k = n is also possible.

    for(int k = 0; k < n; k++) 
    {
        if(A[k] <= n && A[k] >= 0) //No negative numbers!
           numbersUsed[A[k]] = true;
    }

    for(int k = 0; k <= n; k++) 
    {
       if(numbersUsed[k] == false) 
          return k;
    } 
    return -1; //nothing found
 }   

Complexity is 2*n because of the two for loops, giving overall complexity O(n).