[ARRAY] Find one Non-Repeated Element of an Array

Some solutions are:

• Making use of hash, but that would result in linear time complexity but very poor space complexity
• Sorting the list using MergeSort O(nlogn) and then finding the element which doesn't repeat

Use the basic idea of XOR to solve this problem.

"one element appears once, all others an even number of times", then the solution would be to XOR the elements. The reason is that x^x = 0,

so all the paired elements would vanish leaving only the lonely element.

Basically, it makes use of the fact that x^x = 0 and 0^x=x. So all paired elements get XOR'd and vanish leaving the lonely element.

   1: class Solution {

   2: public:

   3:     int singleNumber(int A[], int n) {

   4:         if ( n <= 0 )

   5:             return 0 ;

   6:

   7:         if ( 1 == n )

   8:             return A[0] ;

   9:

  10:         int Num = A[0] ;

  11:         for ( int i = 1; i < n; i++ )

  12:             Num ^= A[i] ;

  13:

  14:         return Num ;

  15:     }

  16: };