Given an array of n integers from 1 to n with one integer repeated twice

Problem - Given an array of n integers from 1 to n with one integer repeated twice
This can be done via normal array traversal or hash table to find duplicates. But since we are given that the integers are from 1 to n, then there are better methods available.

Approach 1 - Arithmetic sum approach
So, the efficient method to solve it calculate the sum of actual input array, and expected sum of the array.
Input: 1,2,3,2,4 => 12
Expected: 1,2,3,4 => 10
Input - Expected => 2

In general, arithmetic sum of series with numbers - 1,2,...n is n(n+1)/2

Approach 2 - Using the xor approach
 XOR method works when we have an element repeated odd number of times, see here, because xor on number for odd number of times results in that number and xor for number for even number of times returns 0.
i.e.
So, this approach will work uses one additional integer to keep the loop counter, and it accesses each array element three times - twice to read it and write it at the current iteration and once to read it for the next iteration.

for(int i=0;i<array.length;i++){
  array[i] = array[i] ^ array[i-1] ^ i;
}
print(array[n-1]);

However array here is destroyed. Running time is again O(n) and because we use counter, so space complexity is O(1).


Lets dry run. (to come soon) 

But we don't what to destroy the array, then we can use a separate variable to maintain duplicate element.

int dupe;
for(int i=0;i<array.length;i++){
  dupe = dupe ^  i  ^array[i] ;
}
print (dupe);

Approach 3 - Sorting 
Sort the array in O(n log n) time and then check if 2 adjacent elements are equal which takes O(n), so overall O(n log n)

Approach 4 - Hashtable
Of-course this is again very simple approach, where we can add the element to the hashtable, and if the element already exists, while adding this is the element. Again it takes O(n). We can also use array, which pretends like hashtable -

//elements from 1-10
int count [10];

for (int i = 0; i < arraylen; i++) {
    count[array[i]]++;
}

Thanks.