# 260 Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note: The order of the result is not important. So in the above example, [5, 3] is also correct. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
//O(N^2) time (SLOW!!!)
#include <iostream>
#include <vector>
using namespace std;
bool doesElementExist(vector<int>& nums, int elem) {
for (int i = 0; i < nums.size(); i++)
if (nums.at(i) == elem) return true;
return false;
}
vector<int> singleNumber(vector<int>& nums) {
vector<int> temp;
int i = 0;
temp.push_back(nums.at(i));
for (i = 1; i < nums.size(); i++) {
if (!doesElementExist(temp, nums.at(i)))
temp.push_back(nums.at(i));
}
return temp;
}
int main()
{
vector<int> nums2 = { 1,2,3,4,5,6,7,8,9,0, 0 };
vector<int> singled = singleNumber(nums2);
for (auto i : singled) cout << i << ' ';
}
//O(NlogN) + O(N) [faster, but still not fast enough]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> singleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int first = 0, second = 1;
int fixedFirst = 0, fixedSecond = 1;
int counterToErase = 1;
bool unique = true;
while (fixedSecond < nums.size())
{
// check if two or more of the same numbers
while (nums.at(first) == nums.at(second)) {
counterToErase++;
second++;
unique = false;
if (second >= nums.size()) break;
}
// there were duplicates
if (!unique) {
// erase the amount counted
nums.erase(nums.begin() + fixedFirst, nums.begin() + counterToErase + fixedFirst);
counterToErase = 1;
first = fixedFirst; second = fixedSecond;
unique = true;
}
// there were no duplicates
else {
first = fixedFirst += 2;
second = fixedSecond += 2;
}
//for (auto i : nums) cout << i << ' '; cout << endl;
}
return nums;
}
int main()
{
vector<int> nums2 = { 1,1,2,3,4,5,6,7,8,9, 0,0,1,2,1,2,2,1,1,2,3,4,1,2,1,2,3,1,12,3,1231,1,31 };
vector<int> singled = singleNumber(nums2);
for (auto i : singled) cout << i << ' ';
}
//O(N), O(1) space
• Here I know that if I first xor all the elements, the return will be the two unique xor'd elements. `x ^ y = (2 unique elements xor'd)`.
• If I can find one of the unique elements, I can find the other, since `(2 unique elements xor'd) ^ x = y`, as the inverse of xor = xor.
• So we've reduced the problem into just finding any one of the first single numbers.
• Doing this isnt really intuitive, we apparently have the first find the first set bit of cum that ill call temp. Then we xor anything in the number of sequence again that is >= temp, inverse of temp, or is zero. This alone will return the first unique element.
vector<int> singleNumber(vector<int>& nums) {
vector<int> singlenum (2);
int cum = 0;
for (auto i : nums) {
cum ^= i;
}
// get first set bit
int temp = cum & -cum;
for (auto i : nums) {
if ((i & temp) == 0)
singlenum ^= i;
}
// x ^ y = cum, inverse of xor = xor
singlenum = singlenum ^ cum;
return singlenum;
}