CareerCup

1. Put numbers between 0 and n-1 to a[number]
2. Process array and if (a[i] != i) -> number "i" is missing
3. Put numbers between n to 2*n-1 to a[number-n]
4. Process array and if (a[i] != i + n) -> number "i + n" is missing

public class AbsentNumbers {

	public static void main(String[] args) {
		int[] array = new int[]{8,4,12,0,7,3,1};
		printAbsentNumbers(array);
	}

	private static void printAbsentNumbers(int[] array) {
		//sort 0 to n-1
		for (int i = 0; i < array.length; i++) {
			if (array[i] < array.length){
				int temp = array[array[i]];
				array[array[i]] = array[i];
				array[i] = temp;
			}
		}
		//check 0 to n-1
		for (int i = 0; i < array.length; i++) {
			if (array[i] != i){
				System.out.print(i + " ");
			}
		}
		//sort n to 2*n-1
		for (int i = 0; i < array.length; i++) {
			if (array[i] >= array.length){
				int temp = array[array[i] - array.length];
				array[array[i] - array.length] = array[i];
				array[i] = temp;
			}
		}
		//check n to 2*n-1
		for (int i = 0; i < array.length; i++) {
			if (array[i] != i + array.length){
				System.out.print(i + array.length + " ");
			}
		}
	}

}

is the array sorted or not ?

Here is an algorithm that takes O(1) space and O(N) time and meets all these weird requirements.

1. take tow variable: index=-1,value=-1.

2. Imp: Traverse the array from i=0 to n-1. If a[i]==i or a[i]==i+n then move ahead else there will be the following cases:
(i) If a[a[i]] ! =a[i] && a[a[i]]!=a[i]+n : Swap a[i] and a[a[i]].
(ii) else if index==-1 : index=i; value=a[i] and a[a[i]]=value
{iii) else a[a[i]]=value;

3. Now again traverse the array and do the following:
(i) If a[i] == value and i==index: Print i and i+n.
(ii) else If a[i] != value && a[i]==i : Print i+n
(iii) else If a[i] != value && a[i]==i+n : Print i 
(iv) else If a[i] !=value : Print i and i+n
(v) else if a[i]==value: continue.

def findmissing(array):
	#trivial cases
	if(len(array) < 1):
		return []
	if(len(array) == 1):
		if(array[0] == 0):
			return [1]
		else:
			return [0]
	#stores output
	outList = []
	if(array[0]==0):
		#don't want to include 0 in the multiplication
		multArr = reduce(lambda x, y: x*y, array[1:])
	else:
		multArr = reduce(lambda x, y: x*y, array)
		outList.append(0)

	#multiply all numbers from 1 to 2*n
	maxTotal = reduce(lambda x, y: x*y, list(range(1,2*len(array))))

	for i in range(2*len(array)-1,0,-1):
		#take care of division by 1... which will of course return true 
		#for all numbers besides 0 (unless multArr is 0 also)
		if(i==1):
			if(array[0]==1 or array[1]==1):
				break
			else:
				outList.append(1)
				break
		if(maxTotal/i >= multArr):#keep dividing by the largest factor
			outList.append(i)
			maxTotal = maxTotal/i
	return outList


#array = [0,2,4]
#array = [1]
array = [0,1,2,3,4,5,6,7]
print(findmissing(array))

Compress array.
{0, 2, 3, 4, 5, 9} => {9, 0, 2, 2, 5, 9}

[2, 2, 5] means [2, 3, 4, 5]. [0, 0, 100] means [0, 1, ..., 100].
If 2n-1 number is stored in not end of array, it is empty space.
Then, you can fill missing number from left to right.

void findMissing(vector<UINT32>& arr) {
	int i, j;
	UINT32 last, start, prev, count, firstFrom, firstTo, secondFrom, secondTo;

	if (arr.size() == 0) return;
	if (arr.size() == 1) {
		arr[0] = (arr[0] + 1) % 2;
		return;
	}

	sort(arr.begin(), arr.end());

	last = arr.size() + arr.size() - 1;

	// find continuous sequence
	start = last;
	prev = last;
	count = 0;
	for (i = 0; i < arr.size(); i++) {
		if (prev + 1 == arr[i]) {
			count++;
			if (count > 3) {
				arr[i - 3] = last;
				arr[i - 2] = start;
				arr[i - 1] = start;
			}
		} else {
			start = arr[i];
			count = 1;
		}
		prev = arr[i];
	}

	// move empty element to first
	for (i = arr.size() - 2; i > 0; i--) {
		if (arr[i] != last) continue;
		for (j = i - 1; j >= 0; j--) {
			if (arr[j] == last) continue;
			arr[i] = arr[j];
			arr[j] = last;
			break;
		}
	}

	// skip empty space
	for (i = 0; i < arr.size(); i++) {
		if (arr[i] != last) break;
	}
	j = 0;
	firstFrom = 0;
	firstTo = 0;
	secondFrom = 0;
	secondTo = 0;
	while (j < arr.size()) {
		// find first empty sequency
		firstFrom = secondTo;
		firstTo = secondTo;
		for (; i < arr.size(); i++) {
			if (arr[i] <= firstFrom || (i > 2 && arr[i - 2] == arr[i - 1])) {
				firstFrom = arr[i] + 1;
				firstTo = last + 1;
			} else {
				firstTo = arr[i];
				break;
			}
		}

		// find second empty sequency
		secondFrom = firstTo;
		secondTo = firstTo;
		for (; i < arr.size(); i++) {
			if (arr[i] <= secondFrom || (i > 2 && arr[i - 2] == arr[i - 1])) {
				secondFrom = arr[i] + 1;
				secondTo = last + 1;
			} else {
				secondTo = arr[i];
				break;
			}
		}
		
		for (; j < arr.size(); j++) {
			if (firstFrom == firstTo) break;
			arr[j] = firstFrom;
			firstFrom++;
		}

		for (; j < arr.size(); j++) {
			if (secondFrom == secondTo) break;
			arr[j] = secondFrom;
			secondFrom++;
		}
	}
}

I think the following solution. Let's split the array in two sets - one that contains elements lower than N [0-N) and other that contains elements greater or equal to N [N,2N-1)
I reorder two sets one after another for the reason to sort each of the sets and iterate all numbers from 0 to 2*N - 1 to print absent elements. Time complexity is O(n) and space complexity o(1)
{{
void swap (int i, int j, int[] data) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}

void findCountInSplit(int[] numbers, int N, boolean lessThanN) {
int index = 0 ;
while (index < numbers.length) {
if (lessThanN) {
if ((numbers[index] < N) && (numbers[index] != index))
swap(index, numbers[index], numbers);
else
index++;
} else {
if ((numbers[index] >= N) && (numbers[numbers[index]-N] != numbers[index]))
swap(index, numbers[index] - N, numbers);
else
index++;
}
}
int upperBound = 0;
int lowerBound = 0;
if (lessThanN) {
upperBound = N;
lowerBound = 0;
}
else {
upperBound = 2*N;
lowerBound = N;
}
for (index = lowerBound ; index < upperBound; index ++) {
if (lessThanN) {
if((numbers[index] >= N)){
System.out.print(index +" ");
}
} else {
if((numbers[index - N] < N)){
System.out.print(index +" ");
}
}
}
}

void printAbsentNumbers(int[] numbers) {
int N = numbers.length;
for (int element : numbers) {
if ((element < 0) || (element > (2 * N - 1)))
throw new IllegalArgumentException();

}
findCountInSplit(numbers,N, true);
findCountInSplit(numbers,N, false);

for(int t:numbers ){
System.out.print(t);
}

}
}}

N cant be arbitrarily large so radix is possible

How about the working of this code ?

public void findMissingNumbers(int[] num) {
        int j=0;
        for(int i=0;i<2*num.length;){
                if(num[j] == i){
                    i = num[j]+1;
                    j++; 
                }
                else{
                        while(i!=num[j]){
                            System.out.println(i);
                            i++;
                        }
                }
        }
    }

How about working of this code ?

public void findMissingNumbers(int[] num) {
        int j=0;
        for(int i=0;i<2*num.length;){
                if(num[j] == i){
                    i = num[j]+1;
                    j++; 
                }
                else{
                        while(i!=num[j]){
                            System.out.println(i);
                            i++;
                        }
                }
        }
    }

Python code:

def find_missing(lst, n):
    lst.insert(0, -1)
    lst.append(2*n)

    print ",".join(["%d-%d" if item2 - item1 > 1 else "%d" \
                    for item1,item2 in zip(lst[:-1], lst[1:])])

I have a solution with time complexity o(n) and space complexity o(1).
Iterate all number from from 0 to 2*n-1(lets call it i) and compare each number with a[j](j start from 0). If current number matches with a[j] then increment j, otherwise output the number i(this one is the missing). If j goes beyond n then just output the number i.

#include<stdio.h>
main()
{
   int arr[]={0,1,4,5};
   // int arr[]={0,2,4};
   // int arr[]={0};
   // int arr[]={};
   int n = sizeof(arr)/sizeof(arr[0]);
   int i,j;
   j=0;
   for (i=0;i<2*n;i++)
   {
     if(j<n)
     {
       if(i == arr[j])
         j++;
       else
         printf("%d,",i);
     }
     else
     {
         printf("%d,",i);
     }
   }
   printf("\n");
}

I have a solution with time complexity o(n) and space complexity o(1).
Iterate the numbers from 0 to 2*n-1(lets call it i) and compare with a[j](j starts from 0). If i and a[j] matches then increment j, otherwise output the number i. If j goes beyond n then just output number i.

#include<stdio.h>
main()
{
   int arr[]={0,1,4,5};
   // int arr[]={0,2,4};
   // int arr[]={0};
   // int arr[]={};
   int n = sizeof(arr)/sizeof(arr[0]);
   int i,j;
   j=0;
   for (i=0;i<2*n;i++)
   {
     if(j<n)
     {
       if(i == arr[j])
         j++;
       else
         printf("%d,",i);
     }
     else
     {
         printf("%d,",i);
     }
   }
   printf("\n");
}

I have a solution with time complexity o(n) and space complexity o(1).
Iterate the numbers from 0 to 2*n-1(lets call it i) and compare with a[j](j starts from 0). If i and a[j] matches then increment j, otherwise output the number i. If j goes beyond n then just output number i.

I have a solution with time complexity o(n) and space complexity o(1).
Iterate the numbers from 0 to 2*n-1(lets call it i) and compare with a[j](j starts from 0). If i and a[j] matches then increment j, otherwise output the number i. If j goes beyond n then just output number i.

#include<stdio.h>
main()
{
   int arr[]={0,1,4,5};
   // int arr[]={0,2,4};
   // int arr[]={0};
   // int arr[]={};
   int n = sizeof(arr)/sizeof(arr[0]);
   int i,j;
   j=0;
   for (i=0;i<2*n;i++)
   {
     if(j<n)
     {
       if(i == arr[j])
         j++;
       else
         printf("%d,",i);
     }
     else
     {
         printf("%d,",i);
     }
   }
   printf("\n");
}

processing each element. Put in each index i, -1: if only i exists, -2, if both i and i + n exist, -3, if only i + n exists, and -4 if none exists.

int a[5] = {1 , 4 , 5 , 7, 2};  
n = 5; 


for (int i = 0; i < n; i++){
	int temp = a[i]; 
	while (temp >= 0 ){
		int temp2 = -4; 
		
		int j = temp % n; 
		if (i == j ) {
			if (temp == j)
				a[i] = -1;  
			else 	
				a[i] = -3; 		
			break; 
		}

		if (a[j] >= 0){
			temp2 = a[j];
			if (j == temp)
				a[j] = -1; 
			else 		
				a[j] = -3;
			temp = temp2;   
		}else if (a[j] == -1 || a[j] == -3){
			a[j] = -2; 
			break; 
		}else if (a[j] == -4){
			if (j == temp)
				a[j] = -1; 
			else 
				a[j] = -3;
			break; 
		}



	}
}

for (int i = 0; i < n; i++){
	int temp = a[i];
	switch(temp):
		case -1:
			cout << i + n << endl; 
			break; 
		case -2: 
			break; 
		case -3:
			cout << i << endl; 
			break;
		case -4:
			cout << i << endl; 
			cout << i + n << endl; 
			break;
		default: 
			cerr << “error in processing all the elements \n” ; 

}

public int[] findMissing(int[] arr)
{
	int tmp=0;
	int start=0;
	int fillIdx=0;
	if(arr[0]!=0)
	{
		int end=arr[0];
		for(int i=0;i<end;i++)
		{
			tmp=arr[i];
			arr[i]=i;
			start++;
		}
	}else
	{
		start++;
		tmp=arr[0];
	}
	while(start<=arr.length-1 && fillIdx<arr.length-1)
	{
		if(arr[start]-tmp>1)
		{
			for(int i=tmp+1;i<arr[start];i++)
			{
				arr[fillIdx++]=i;
			}
			tmp=arr[start++];
		}else
		{
			tmp=arr[start++];
		}
	}
	
	for(int i=tmp+1; i<2*arr.length && fillIdx<arr.length)
	{
		arr[fillIdx++]=tmp
		
	}
	return arr;

}

Here is my solution, I have tested it and it works

Step I: Find missing numbers less than n
Loop through the array( i ), if (a[i] != i && i < n) => put i in the i'th position, and do the same for the item that was in the i'th position. This second loop ends either when you have an item that is in it's correct position or you see a number greater than n.

Step 2: Find missing numbers greater than or equal to numbers
Similar approach :)

here's the code

#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include<conio.h>

using namespace std;

int MissingNumbers( std::vector<int> * original_p, std::vector<int> * missing_p )
{
   size_t n = original_p->size();

   int current;
   int temp;
   size_t i;

   for ( i = 0 ; i < n ; i++ )
   {
      current = original_p->at(i);

      while ( 1 )
      {
         if ( ( current < n ) && ( original_p->at(current)!=current ) )
         {
            temp = original_p->at(current);
            original_p->at(current) = current;
            current = temp;
         }
         else
         {
            break;
         }
      }

      if ( current >= n )
      {
         original_p->at(i) = current;
      }
   }

   for ( i = 0 ; i < n ; i++ )
   {
      if ( original_p->at(i)!=i ) 
      {
         missing_p->push_back( i );
      }
   }


   for ( i = 0 ; i < n ; i++ )
   {
      current = original_p->at(i);

      while ( 1 )
      {
         if ( ( current >= n ) && ( original_p->at(current-n)!=current ) )
         {
            temp = original_p->at(current-n);
            original_p->at(current-n) = current;
            current = temp;
         }
         else
         {
            break;
         }
      }

      if ( current < n )
      {
         original_p->at(i) = current;
      }
   }

   for ( i = 0 ; i < n ; i++ )
   {
      if ( original_p->at(i)!=i+n ) 
      {
         missing_p->push_back( i+n );
      }
   }

   return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
   std::vector<int> Original;
   std::vector<int> Missing;

   int i,j,k,temp;

   int x,y;

   int array_size;

   for ( i = 0 ; i < 100 ; i++ )
   {
      Original.clear();
      Missing.clear();

      array_size = rand()%5 + 3;

      for ( j = 0 ; j < array_size ; j++ )
      {
         if ( rand()%2 )
         {
            Original.push_back(j);
         }
         else
         {
            Original.push_back(j+array_size);
         }
      }

      //scramble

      for ( k = 0 ; k < 100 ; k++ )
      {
         x = rand()%array_size;
         y = rand()%array_size;

         temp = Original[x];
         Original[x] = Original[y];
         Original[y] = temp;
      }


      //print original
      cout << endl << "-----------------------" << endl << "Original  Array: " ;
      for ( j = 0 ; j < array_size ; j++ )
      {
         cout << Original[j] << ", ";
      }

      cout << endl;

      MissingNumbers( &Original, &Missing );

      //Print Missing
      cout << "Missing Numbers: " ;
      for ( j = 0 ; j < array_size ; j++ )
      {
         cout << Missing[j] << ", ";
      }
   }
   
   getch();
	return 0;
}

and samples:

-----------------------
Original Array: 0, 5, 3, 6,
Missing Numbers: 1, 2, 4, 7,
-----------------------
Original Array: 3, 12, 8, 13, 11, 9, 0,
Missing Numbers: 1, 2, 4, 5, 6, 7, 10,
-----------------------
Original Array: 2, 0, 4,
Missing Numbers: 1, 3, 5,
-----------------------
Original Array: 8, 9, 13, 5, 0, 11, 3,
Missing Numbers: 1, 2, 4, 6, 7, 10, 12,
-----------------------
Original Array: 2, 3, 4,
Missing Numbers: 0, 1, 5,
-----------------------
Original Array: 4, 7, 5, 6,
Missing Numbers: 0, 1, 2, 3,
-----------------------
Original Array: 0, 5, 4,
Missing Numbers: 1, 2, 3,
-----------------------
Original Array: 3, 2, 4, 5,
Missing Numbers: 0, 1, 6, 7,
-----------------------
Original Array: 4, 1, 7, 2,
Missing Numbers: 0, 3, 5, 6,
-----------------------
Original Array: 7, 11, 6, 4, 9, 8,
Missing Numbers: 0, 1, 2, 3, 5, 10,
-----------------------
Original Array: 0, 11, 9, 2, 4, 7,
Missing Numbers: 1, 3, 5, 6, 8, 10,
-----------------------
Original Array: 4, 6, 2, 0, 3,
Missing Numbers: 1, 5, 7, 8, 9,
-----------------------
Original Array: 4, 0, 5,
Missing Numbers: 1, 2, 3,
-----------------------
Original Array: 0, 7, 6, 5,
Missing Numbers: 1, 2, 3, 4,
-----------------------
Original Array: 3, 2, 6, 5, 9,
Missing Numbers: 0, 1, 4, 7, 8,
-----------------------
Original Array: 0, 6, 7, 8, 9,
Missing Numbers: 1, 2, 3, 4, 5,
-----------------------
Original Array: 8, 13, 5, 3, 7, 11, 9,
Missing Numbers: 0, 1, 2, 4, 6, 10, 12,
-----------------------
Original Array: 6, 7, 5, 4, 3,
Missing Numbers: 0, 1, 2, 8, 9,
-----------------------
Original Array: 8, 1, 0, 4, 2,
Missing Numbers: 3, 5, 6, 7, 9,
-----------------------
Original Array: 8, 9, 5, 10, 0, 7,
Missing Numbers: 1, 2, 3, 4, 6, 11,
-----------------------
Original Array: 0, 5, 2, 3,
Missing Numbers: 1, 4, 6, 7,
-----------------------
Original Array: 1, 0, 2,
Missing Numbers: 3, 4, 5,
-----------------------
Original Array: 7, 5, 10, 6, 3, 2,
Missing Numbers: 0, 1, 4, 8, 9, 11,
-----------------------
Original Array: 2, 5, 6, 4, 3,
Missing Numbers: 0, 1, 7, 8, 9,
-----------------------
Original Array: 4, 6, 1, 2, 9, 11,
Missing Numbers: 0, 3, 5, 7, 8, 10,
-----------------------
Original Array: 7, 0, 6, 1,
Missing Numbers: 2, 3, 4, 5,
-----------------------
Original Array: 3, 4, 5,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 6, 8, 5, 4, 2,
Missing Numbers: 0, 1, 3, 7, 9,
-----------------------
Original Array: 0, 8, 7, 6, 4,
Missing Numbers: 1, 2, 3, 5, 9,
-----------------------
Original Array: 3, 2, 1,
Missing Numbers: 0, 4, 5,
-----------------------
Original Array: 11, 12, 3, 2, 13, 1, 7,
Missing Numbers: 0, 4, 5, 6, 8, 9, 10,
-----------------------
Original Array: 1, 7, 4, 5, 8,
Missing Numbers: 0, 2, 3, 6, 9,
-----------------------
Original Array: 6, 4, 5, 7,
Missing Numbers: 0, 1, 2, 3,
-----------------------
Original Array: 4, 0, 2,
Missing Numbers: 1, 3, 5,
-----------------------
Original Array: 2, 0, 4,
Missing Numbers: 1, 3, 5,
-----------------------
Original Array: 3, 12, 6, 9, 11, 8, 0,
Missing Numbers: 1, 2, 4, 5, 7, 10, 13,
-----------------------
Original Array: 0, 4, 5,
Missing Numbers: 1, 2, 3,
-----------------------
Original Array: 1, 11, 2, 3, 10, 0,
Missing Numbers: 4, 5, 6, 7, 8, 9,
-----------------------
Original Array: 9, 8, 7, 4, 5, 6,
Missing Numbers: 0, 1, 2, 3, 10, 11,
-----------------------
Original Array: 3, 4, 1, 2,
Missing Numbers: 0, 5, 6, 7,
-----------------------
Original Array: 0, 5, 1,
Missing Numbers: 2, 3, 4,
-----------------------
Original Array: 4, 5, 2, 3,
Missing Numbers: 0, 1, 6, 7,
-----------------------
Original Array: 4, 2, 3,
Missing Numbers: 0, 1, 5,
-----------------------
Original Array: 10, 8, 7, 9, 6, 11,
Missing Numbers: 0, 1, 2, 3, 4, 5,
-----------------------
Original Array: 3, 5, 4,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 3, 12, 11, 9, 0, 8, 13,
Missing Numbers: 1, 2, 4, 5, 6, 7, 10,
-----------------------
Original Array: 2, 1, 7, 4,
Missing Numbers: 0, 3, 5, 6,
-----------------------
Original Array: 10, 1, 7, 6, 2, 12, 4,
Missing Numbers: 0, 3, 5, 8, 9, 11, 13,
-----------------------
Original Array: 4, 0, 5, 7, 8, 9,
Missing Numbers: 1, 2, 3, 6, 10, 11,
-----------------------
Original Array: 13, 1, 11, 9, 10, 7, 5,
Missing Numbers: 0, 2, 3, 4, 6, 8, 12,
-----------------------
Original Array: 4, 5, 3,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 7, 8, 6, 3, 10, 11,
Missing Numbers: 0, 1, 2, 4, 5, 9,
-----------------------
Original Array: 1, 3, 6, 10, 8, 11,
Missing Numbers: 0, 2, 4, 5, 7, 9,
-----------------------
Original Array: 1, 0, 11, 2, 4, 9,
Missing Numbers: 3, 5, 6, 7, 8, 10,
-----------------------
Original Array: 6, 7, 0, 1,
Missing Numbers: 2, 3, 4, 5,
-----------------------
Original Array: 1, 0, 2, 3,
Missing Numbers: 4, 5, 6, 7,
-----------------------
Original Array: 2, 8, 5, 6, 3, 11, 7,
Missing Numbers: 0, 1, 4, 9, 10, 12, 13,
-----------------------
Original Array: 9, 13, 5, 7, 1, 3, 11,
Missing Numbers: 0, 2, 4, 6, 8, 10, 12,
-----------------------
Original Array: 7, 8, 0, 6, 9,
Missing Numbers: 1, 2, 3, 4, 5,
-----------------------
Original Array: 6, 4, 7, 2, 3, 11,
Missing Numbers: 0, 1, 5, 8, 9, 10,
-----------------------
Original Array: 0, 4, 5,
Missing Numbers: 1, 2, 3,
-----------------------
Original Array: 1, 9, 10, 5, 0, 2,
Missing Numbers: 3, 4, 6, 7, 8, 11,
-----------------------
Original Array: 6, 5, 7, 3, 4,
Missing Numbers: 0, 1, 2, 8, 9,
-----------------------
Original Array: 5, 4, 6, 1, 2, 3, 7,
Missing Numbers: 0, 8, 9, 10, 11, 12, 13,
-----------------------
Original Array: 8, 2, 5, 4, 1,
Missing Numbers: 0, 3, 6, 7, 9,
-----------------------
Original Array: 6, 8, 7, 2, 5, 3, 4,
Missing Numbers: 0, 1, 9, 10, 11, 12, 13,
-----------------------
Original Array: 4, 3, 2, 5,
Missing Numbers: 0, 1, 6, 7,
-----------------------
Original Array: 7, 4, 6, 0, 8,
Missing Numbers: 1, 2, 3, 5, 9,
-----------------------
Original Array: 5, 3, 4,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 1, 6, 0, 3,
Missing Numbers: 2, 4, 5, 7,
-----------------------
Original Array: 5, 0, 1,
Missing Numbers: 2, 3, 4,
-----------------------
Original Array: 5, 1, 3,
Missing Numbers: 0, 2, 4,
-----------------------
Original Array: 9, 7, 3, 5, 1,
Missing Numbers: 0, 2, 4, 6, 8,
-----------------------
Original Array: 3, 0, 2, 1,
Missing Numbers: 4, 5, 6, 7,
-----------------------
Original Array: 12, 2, 1, 11, 13, 10, 0,
Missing Numbers: 3, 4, 5, 6, 7, 8, 9,
-----------------------
Original Array: 4, 5, 3,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 4, 6, 2, 1, 10, 5, 7,
Missing Numbers: 0, 3, 8, 9, 11, 12, 13,
-----------------------
Original Array: 4, 3, 2,
Missing Numbers: 0, 1, 5,
-----------------------
Original Array: 0, 13, 1, 12, 10, 11, 2,
Missing Numbers: 3, 4, 5, 6, 7, 8, 9,
-----------------------
Original Array: 3, 6, 5, 7, 2, 10,
Missing Numbers: 0, 1, 4, 8, 9, 11,
-----------------------
Original Array: 4, 0, 2,
Missing Numbers: 1, 3, 5,
-----------------------
Original Array: 12, 2, 6, 7, 1, 11, 10,
Missing Numbers: 0, 3, 4, 5, 8, 9, 13,
-----------------------
Original Array: 0, 4, 2, 5, 7, 3,
Missing Numbers: 1, 6, 8, 9, 10, 11,
-----------------------
Original Array: 3, 2, 1, 9, 0,
Missing Numbers: 4, 5, 6, 7, 8,
-----------------------
Original Array: 1, 5, 3, 8, 6, 10,
Missing Numbers: 0, 2, 4, 7, 9, 11,
-----------------------
Original Array: 0, 2, 1,
Missing Numbers: 3, 4, 5,
-----------------------
Original Array: 0, 5, 1,
Missing Numbers: 2, 3, 4,
-----------------------
Original Array: 8, 7, 9, 5, 6,
Missing Numbers: 0, 1, 2, 3, 4,
-----------------------
Original Array: 3, 7, 6, 8, 10, 5,
Missing Numbers: 0, 1, 2, 4, 9, 11,
-----------------------
Original Array: 8, 7, 10, 2, 6, 11, 5,
Missing Numbers: 0, 1, 3, 4, 9, 12, 13,
-----------------------
Original Array: 4, 8, 0, 5, 7, 3,
Missing Numbers: 1, 2, 6, 9, 10, 11,
-----------------------
Original Array: 0, 7, 6, 4, 8,
Missing Numbers: 1, 2, 3, 5, 9,
-----------------------
Original Array: 5, 1, 0,
Missing Numbers: 2, 3, 4,
-----------------------
Original Array: 10, 6, 2, 3, 11, 1,
Missing Numbers: 0, 4, 5, 7, 8, 9,
-----------------------
Original Array: 8, 13, 9, 3, 0, 4, 12,
Missing Numbers: 1, 2, 5, 6, 7, 10, 11,
-----------------------
Original Array: 0, 9, 1, 4, 10, 6, 12,
Missing Numbers: 2, 3, 5, 7, 8, 11, 13,
-----------------------
Original Array: 7, 5, 0, 2,
Missing Numbers: 1, 3, 4, 6,
-----------------------
Original Array: 4, 5, 3,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 2, 1, 5, 4, 0, 9,
Missing Numbers: 3, 6, 7, 8, 10, 11,
-----------------------
Original Array: 0, 6, 9, 2, 8,
Missing Numbers: 1, 3, 4, 5, 7,

Use bitwise OR.
First: Assuming n <= 16 (we'll talk about n>16 after, but it's easier to understand with this constraint.

1) initialize int x = 0
2) iterate through input array, and for each a[i] just do: x = x | (1 << a[i]);
Ex: if a[i] == 3, then x = x | (1 << 3), which puts a 1 in the 4th bit.
3) At the end of iteration, there will be a 1 in each bit that exists and a 0 in each bit that is missing. O(n)
4) Build the answer array (which you already know is size n) by x&(1 << i) in a for loop with i = 0 to n. This has the added bonus that the resulting array is sorted. O(n)

Final time complexity: O(2n) = O(n)
Final space complexity: O(1)

5) Instead of step 1, initialize an int[] x = new int[n/16]

Should be fairly simple to write code to do the above

int[] input = new int[] {0, 2, 4}; //given input, range should have [0->5]

int indexInInput = 0;

for(int i = 0; i < 2 * input.Length; i++)
{
if(i = input[indexInInput])
{
//skip
indexInInput++;
}
else
{
Console.WriteLine(i);
}

Time: O(n), Space: O(n)

public static int[] getMissingArr(int[] a) {
	if (a == null) {
		return null;
	}
	int n = a.length * 2;
	
	boolean present[] = new boolean[n];
	int i = 0, j = 0;
	int numMissing = n;
	
	for (i = 0; i < a.length; i++) {
		present[a[i]] = true;
		numMissing--;
	}
	
	i = 0;
	j = 0;
	int[] r = new int[numMissing];
	while(i < present.length && j < r.length) {
		if (!present[i]) {
			r[j] = i;
			j++;
		}						
		i++;
	}
	return r;				
}

public void printNotInArr(int[] arr) {

	if(arr == null)
		return null;
		
	int len = arr.length;
	int max = 2 * len;
	
	for(int i = 0; i < len; i++) {
		System.out.println(max - arr[i] - 1);
	}
}

public void printNotInArr(int[] arr) {

	if(arr == null)
		return null;
		
	int len = arr.length;
	int max = 2 * len;
	
	for(int i = 0; i < len; i++) {
		System.out.println(max - arr[i] - 1);
	}
}

vector<int> findMissing(vector<int> arr, int n){

priority_queue(int, vector<int>, greater<int>) min_heap;

vector<int> result;

for(int i=0; i<n; i++){
min_heap.push(arr[i]);    
}

int prev = 0;

while(!min_heap.empty()){

int temp = min_heap.top();
min_heap.pop();

while(temp-prev > 0){
result.push_back(++prev);
}
prev = temp;
    
}

//Add all elements that are greater than last element but smaller than 2*n
while(prev < 2*n -1){
result.push_back(++prev);
}

return result;

}

vector<int> findMissing(vector<int> arr, int n){

priority_queue(int, vector<int>, greater<int>) min_heap;

vector<int> result;

for(int i=0; i<n; i++){
min_heap.push(arr[i]);    
}

int prev = 0;

while(!min_heap.empty()){

int temp = min_heap.top();
min_heap.pop();

while(temp-prev > 0){
result.push_back(++prev);
}
prev = temp;
    
}

//Add all elements that are greater than last element but smaller than 2*n
while(prev < 2*n -1){
result.push_back(++prev);
}

return result;

}