Example 1: Input: [1,1,3,1] Output: 3
We can solve this by 2 methods:
- unordered_map
- XOR operation.
The solution for “unordered_map” is same as the solution for “single-number”.
Below explains in details about the solution using BIT Manipulation.
If the problem were this: “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. If we tried the same tactic here, we would be left with the XOR of distinct elements, which is not what we want.
Instead, the algorithm above does the following:
ones is the XOR of all elements that have appeared exactly once so far
twos is the XOR of all elements that have appeared exactly twice so far
Each time we take x to be the next element in the array, there are three cases:
if this is the first time x has appeared, it is XORed into ones
if this is the second time x has appeared, it is taken out of ones (by XORing it again) and XORed into twos
if this is the third time x has appeared, it is taken out of ones and twos.
Therefore, in the end, ones will be the XOR of just one element, the lonely element that is not repeated. There are 5 lines of code that we need to look at to see why this works: the five after x = A[i].
#include<iostream> #include<vector> #include<unordered_map> using namespace std; int solution_using_unordered_map(vector<int> &nums) { unordered_map<int,int>mp; for(int i = 0;i < nums.size();i++) mp[nums[i]]++; unordered_map<int,int>::iterator it; for(it = mp.begin();it != mp.end();it++) { if(it->second < 3) return it->first; } } int solution_using_Bit_Manipulation(vector<int> &nums) { int ones = 0; int twos =0; int common_bit_mask; for(int i=0; i<nums.size();i++) { twos= twos|(ones&nums[i]); ones=ones^nums[i]; common_bit_mask= ~(ones&twos); ones &=common_bit_mask; twos &=common_bit_mask; } return ones; } int main() { vector<int> nums; nums.push_back(1); 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_Bit_Manipulation(nums)<<endl; return 0; }
Output:
The result using unordered_map = 2
The result using XOR = 2