# Single Number - C++ Solution

• Approach 1: Using HashTable [Accepted]

Concept:

Store all seen elements in Hash Table with number of times the element is seen as the value corresponding to each key. At the end when all the elements are stored in hash table iterate over hash table and find value where key value is 1.

Algorithm:

1. Initialize a empty hash table.
2. Iterate over `nums`. If current element is present in hash table then increment value corresponding to current element by 1. Else make entry in hash table with current element as key and it's value as 1.
3. Once all the elements of `nums` are seen then iterate over hash table to find which element has single occurrence.

Code:

``````int singleNumber(vector<int>& nums){

std::map<int,int> table;

for (auto x: nums){
if(table.find(x) == table.end()){
table[x] = 1;
}
else{
++table[x];
}

}

for(auto x : table){
if(x.second == 1){
return x.first;
}
}
return -1;
}
``````

Complexity:

• Space Complexity: O(n)
• Time Complexity: O(n)

Approach 2: Using XOR [Accepted]

Concept:

Bitwise XOR exhibits below properties:

• a ^ 0 = a
• a ^ a = a

As all the numbers except one number are present twice, so XOR'ing all the elements of `nums` would give us the single number in `nums`.

Algorithm:

2. Iterate over each element of `nums` and perform XOR of `result` with current element.
3. Return result.

Code:

``````#include<algorithm>
#include<numeric>

int singleNumber(vector<int>& nums){
return std::accumulate(nums.begin(),nums.end(),0,std::bit_xor<int>() );
}
``````

Complexity:

• Space Complexity: O(1)
• Time Complexity: O(n)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.