Example 1: Input: [2,2,1] Output: 1
We can solve this by 2 methods:
- unordered_map
- XOR operation.
We shall discuss both of the solutions in this tutorial.
-
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.
-
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++
#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
No Responses