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[0] ^= i;
    }

    // x ^ y = cum, inverse of xor = xor
    singlenum[1] = singlenum[0] ^ cum;

    return singlenum;
}