Given an array of integers, every element appears twice except for one. Find that single one.

 

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: };