CareerCup

Question is not clear. Please, give an example.

we have numbers from 1-100 unsorted in an array
let say some numbers are missing from it. We have to find them.

I don't think it can be done with constant memory independent of n and k.

We can get number of elements i.e. value of K using the input constraints.
The three varaibles will be Min, Max and Length for the Array which can all computed in a single parse i.e. O(n).
So value of K = (Max-Min)-Lenght.

Still what this K elements are is a mystery spot!!!

We can get number of elements i.e. value of K using the input constraints.
The three varaibles will be Min, Max and Length for the Array which can all computed in a single parse i.e. O(n).
So value of K = (Max-Min)-Lenght.

Still what this K elements are is a mystery spot!!!

Here 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);
}