Finding missing elements in an array

Question

Given you have an array A[1..n] of size n, it contains elements from the set {1..n}. However, two of the elements are missing, (and perhaps two of the array elements are repeated). Find the missing elements.

Eg if n=5, A may be A[5] = {1,2,1,3,2}; and so the missing elements are {4,5}

The approach I used was:

int flag[n] = {0};  
int i;  
for(i = 0; i < n; i++)  {  
  flag[A[i]-1] = 1;  
 }  

for(i = 0; i < n; i++)  {  
 if(!flag[i]) {  
    printf("missing: %d", (i+1));  
}  

the space complexity comes to O(n). I feel this is a very kiddish and inefficient code. So could you please provide a better algo with better space and time complexity.

Answer 1

As @j_random_hacker pointed out, this is quite similar to Finding duplicates in O(n) time and O(1) space, and an adaptation of my answer there works here too. In pseudo-code:

for i := 1 to n
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end if
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

The first loop permutes the array so that if element x is present at least once, then one of those entries will be at position A[x].

Note that although it has a nested loop, it still runs in O(N) time - a swap only occurs if there is an i such that A[i] != i, and each swap sets at least one element such that A[i] == i, where that wasn't true before. This means that the total number of swaps (and thus the total number of executions of the while loop body) is at most N-1.