Find the missing number with minimum complexity

Problem

You have 2 arrays, one array A contains 20000 nos and all numbers are distinct and are in random order. Second array B contains 19999 numbers and it is the subset of the array A. Find the number which is in A but not in B.

Answer

Use XOR and compexity is O(n)

@algo

Let arr1 and arr2 be the arrays with 20000 and 19999 elements respectively.

int temp=0;

for(int j=0;j<20000;j++)
    temp^=arr1[j]; ///Is O(n)

for(int j=0;j<19999;j++)
   temp^=arr2[j]; ////Is also O(n)

Now temp contains the missing element.

PS : I got this problem / algorithm from one of my friend. And here is my sample C# code which verifies it, I have used the arrays of sizes 5 and 4:

using System;
namespace ConsoleApplication1
{
class Program
{
 static void Main(string[] args)
 {
   int[] arr1 = { 1, 2, 3, 4, 5 };
   int[] arr2 = { 1, 3, 4, 5 };
   int temp = 0 ;

   for (int j = 0; j < 5; j++)
      temp ^= arr1[j]; ///Is O(n)

   for (int j = 0; j < 4; j++)
      temp ^= arr2[j]; ////Is also O(n)

   Console.WriteLine(temp);
   Console.ReadKey();
 }
}
}

The output is : 2