CareerCup

a one-pass algorithm is possible.
scan the array and compute the sum and the squared sum.
let's say x and y are two missing numbers.
now that you know x+y and x^2+y^2, you can recover x and y.

using the same trick, you can solve the problem of three numbers being missing.
(right, just compute the cubic sum!)

/* The output of this function is stored at *x and *y */
void getTwoElements(int arr[], int n, int *x, int *y) {
  int xor1;   /* Will hold xor of all elements and numbers from 1 to n */
  int set_bit_no;  /* Will have only single set bit of xor1 */
  int i;
  *x = 0;
  *y = 0;

  xor1 = arr[0];

  /* Get the xor of all array elements elements */
  for(i = 1; i < n; i++)
     xor1 = xor1^arr[i];

  /* XOR the previous result with numbers from 1 to n+2*/
  for(i = 1; i <= n+2; i++)
     xor1 = xor1^i;

  /* Get the rightmost set bit in set_bit_no */
  set_bit_no = xor1 & ~(xor1-1);

  /* Now divide elements in two sets by comparing rightmost set
   bit of xor1 with bit at same position in each element. Also, get XORs
   of two sets. The two XORs are the output elements.
   The following two for loops serve the purpose */
  for(i = 0; i < n; i++) {
    if(arr[i] & set_bit_no)
     *x = *x ^ arr[i]; /* arr[i] belongs to first set */
    else
     *y = *y ^ arr[i]; /* arr[i] belongs to second set*/
  }

  for(i = 1; i <= n+2; i++) {
    if(i & set_bit_no)
     *x = *x ^ i; /* i belongs to first set */
    else
     *y = *y ^ i; /* i belongs to second set*/
  }

  /* Now *x and *y hold the desired output elements */
}

Are the random numbers drawn from the range 1 to 100?

In this case you can use a bit vector of length 100. Set all bits to 0. Iterate over the input: for every number i in the input set bits[i] to 1. Then iterate over the bits to find the missing numbers. Their bits are still 0.

n*(n+1)*(2n+1)/6

Using XOR,
1. XOR all element given in array (98 in count) AND also numbers 1 to 100.
2. Resultant XOR will be the XOR of two missing elements (x^y)
3. Get the position of first rightmost (LSB side) bit set in above result, say it is 2nd position.
4. Divide all elements (array elements and the range elements) in two sets.
5. 1st set will have all elements where 2nd bit is ZERO. XOR of all these elements in this set will one missing value.
6. 2nd set will have all elements where 2nd bit is ONE. XOR of all these elements will give 2nd missing value.

#include <stdio.h>

int main(int argc, char *argv[])
{
int xor=0;
int i, x=0, y=0;
int len=10;
//Taking range as 1-10 where 4 and 7 are missing
int a[10] = {1,2,3,5,6,8,9,10};

//This is XOR of given array elements and all elements in the range
for(i=0;i<len-2;i++)
{
xor ^= a[i];
xor ^= (i+1);
}
xor ^= (len-1);
xor ^= len;

//Get the position of first rightmost (LSB side) bit set in xor
int p = 0;
while(xor)
{
if(xor&1)
break;
else
{
p++;
xor >>= 1;
}
}
printf("p=%d\n",p);

//Divide all elements into 2 sets and take XOR of them
for(i=0;i<len-2;i++)
{
if(a[i] & 1 << p)
x ^= a[i];
else
y ^= a[i];

if((i+1) & 1 << p)
x ^= (i+1);
else
y ^= (i+1);
}
if((len-1) & 1 << p)
x ^= (len-1);
else
y ^= (len-1);

if(len & 1 << p)
x ^= len;
else
y ^= len;

printf("x=%d y=%d\n",x,y);
return 0;
}

Similiar to bit one but uses space. U can find any missing value

int arr[] = {1,2,4,5,7,8,9,10};
boolean arr1[] = new boolean[11];

int sum,totalsum;
void method1() {
for(int i =0;i<arr.length;i++) {
arr1[arr[i]] = true;
}
System.out.println();
for(int i =1;i<arr1.length;i++) {

if(arr1[i] !=true) {
System.out.print(" "+ i);
}

}
}

First, assuming that missing numbers are filled in by duplicates of other numbers.
Here's an inplace algorithm:

-> for every element in the array:
    :swap elements into their corresponding positions.
        ->if an element already exists in the right position then it is a duplicate so set it to -1
    :traverse the array for '-1's and those positions are missing numbers.

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