# 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!!!)

```cpp
#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]

```cpp
#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.

```cpp
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;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/260_single_number_iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.