Arrays

You are given an array with integers between 1 and 1,000,000. One integer is in the array twice. How can you determine which one? Can you think of a way to do it using little extra memory.
Algo:

• Solution 1:
  1. Have a hash table
  2. Iterate through array and store its elements in hash table
  3. As soon as you find an element which is already in hash table, it is the dup element
  Pros:
  • It runs in O(n) time and with only 1 pass
  Cons:
  • It uses O(n) extra memory
• Solution2:
  1. Sort the array using merge sort (O(nlogn) time)
  2. Parse again and if you see a element twice you got the dup.
  Pros:
  • it doesn't use extra memory
  Cons:
  • Running time is greater than O(n)