Interview Question
Software Engineer / DevelopersHere is the code that takes care of duplicates as well. Complexity O(n). If swap() is done inline, it will take only 1 extra space (int tmp). Plus 1 for 'int i' and plus 1 for 'int size'. So not more than 3 variable used. :-)
#include <stdio.h>
void swap(int *a, int *b)
{
int tmp = *a; *a = *b; *b = tmp;
}
void find_missing(int *a, int size)
{
int i = 0;
for (i=1; i<=size; i++) {
while (a[i-1] != -1 && a[i-1] != i && a[a[i-1]-1] != a[i-1]) {
swap(&a[i-1], &a[a[i-1]-1]);
}
}
for (i=0; i<size; i++)
if (a[i] != i+1)
printf("%d ", i+1);
}
int main()
{
#define SIZE 12
/* array with enough space for n elements
extra space padded with -1*/
int a[SIZE] = {6,4,9,4,5,8,3,11,-1,-1,-1,-1};
find_missing(a, SIZE);
}
Question is not clear. Please, give an example.
- fiddler.g July 11, 2010