Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

We can solve this by 2 methods:

1. unordered_map
2. XOR operation.

We shall discuss both of the solutions in this tutorial.

1. Solution using unordered_map.

Use unordered_map, increment the “second” in unordered_map when ever you get an element. At the end, iterate throughout the map, then get the index whose count is 1.

2. Solution using XOR Operation:

The principle of XOR is if two bits are same, then the result is 0, else if two bits are different (0, 1 or 1, 0)then the result is 1.

For example, we have 3 numbers:
9, 3, 9
Binary representation will be:
1001, 0011, 1001

Hence

step 1: 1001^0011 = 1010
step 2: 1010^1001 = 0011

The result will be “0011” i.e 3.

Solution in C++

/*
* File     : single_number.cpp
*/

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

int solution_using_unordered_map(vector<int> &nums) 
{
  unordered_map<int,int> umap;

  //iterate through the nums array
    for(int i:nums)
    {
      // increment the value at the index of the number
        umap[nums[i]]++;
    }

    //initiate an iterator
    unordered_map<int, int>::iterator it=umap.begin();

    //Iterate through out the array
    while(it!=umap.end())
    {
      // if you find a count at an index == 1, return that index.
        if(it->second == 1)
            return it->first;
        it++;
    }

    return -1;
}



int solution_using_XOR(vector<int> &nums) 
{
    
    for(int i = 1; i < nums.size(); ++i) 
      nums[0] ^= nums[i];

    return nums[0];
}

int main()
{
  vector<int> nums;
  nums.push_back(1);
  nums.push_back(1);
  nums.push_back(2);

  cout<<"The result using unordered_map = "<<solution_using_unordered_map(nums)<<endl;
  cout<<"The result using XOR = "<<solution_using_XOR(nums)<<endl;

return 0;

}

Output:

The result using unordered_map = 2
The result using XOR = 2