CareerCup

ith bit of missing element would be :

zor of ith bit of all element in list and ith bit of 1 to n. So all duplicates will be nullified and missing elements bit will remain. Here is the quick code(may be buggy :))

for(i=0;i<32;i++)
{
  ithBit = 0;
  
  //xor with array elements
  for(int k=0; k<n; k++)
  {
    ithBit ^= A[(k+1)*32-1];
  }
  
  //Xor with 1 to n
  for(int k=1; k<=n; k++)
  {
     ithBit = (k & (1<<i))>>i;
  }

  result[i] = ithBit;
}

result[i] will be a 32 bit array having missing element. Hope it helps.

I din get the question yet.

@binu
How can we identify the value of A[i] with just log(A[i]) operations ?For example if the input is 7 ie. 111 I need 3 read operations to identify that I have read 7. but 3 is greater than log7

we can find the missing number by counting the number of bits set at each bit position for all the n-1 numbers. i.e add up numbers of bits set at bit 0 of all numbers. and Do the same for bit1, bit2 etc.
If n is a power of 2 , it will be easier to arrive at a solution. If not then we need bit more logic to calculate it. Run through with sample input to know what i mean.

Let C = Xor of all the elements from 1 to n. O(n) time. Let C' = Xor of the elements read in....let each element have t bits (on average) . So, time taken = n*t*n. Let A = missing no. C = A XOR C'. So, A = C XOR C'.

For solving the above algorithm we will need to use the concept of xor we will xor all the array elements and also xor all the numbers from 1 to n and finally xor both the xor of arrays and numbers together.

Implementation:

int findmissing(int arr[], int n){
int xor_number = 1;
int xor_array = arr[0];
for(int i = 2; i <= n + 1; i++)
	xor_number = xor_number ^ i;
for(int i = 1; i < n; i++)
	xor_array = xor_array ^ arr[i];
return xor_array ^ xor_number;

read a[i] in log(a[i])...this is insane

don't get the question

This is in the CareerCup Cracking the Coding interview and the solution is fairly clever.

add 'em up and subtract it from n(n+1)/2

this is the problem discussed in programming pearl, apply binary search based on bit set.