# 260. Single Number III

## Problem Statement

<br>

Given an integer array `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. You can return the answer in **any order**.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [1,2,1,3,2,5]
</strong><strong>Output: [3,5]
</strong><strong>Explanation:  [5, 3] is also a valid answer.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [-1,0]
</strong><strong>Output: [-1,0]
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [0,1]
</strong><strong>Output: [1,0]
</strong></code></pre>

&#x20;

**Constraints:**

* `2 <= nums.length <= 3 * 104`
* `-231 <= nums[i] <= 231 - 1`
* Each integer in `nums` will appear twice, only two integers will appear once.

## Intuition

```
Approach 1:
Hash map and count

Approach 2: Bit manipulation
Bascially,

The two numbers are not same, so they are going to differ by one position
So that bit will be set

So just divide in two groups based on thar bit

One can find the lowest different bit by
num & -num
where -num is twos complement
You can do this by right shift

Take xor of all group numbers and you get answer

```

### Links

<https://leetcode.com/problems/single-number-iii/description/>

### Video Links

<https://www.youtube.com/watch?v=wPBKH1jy0_E&ab_channel=Codebix>

### Approach 1:

```
Bit MAnipulation
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long int x_or = 0;
        vector<int> ans(2,0);

        for(int i=0; i<nums.size(); i++)
            x_or ^= nums[i];

        long int lowest_bit_set = x_or & -x_or;

        for(auto &it: nums){
            if(it & lowest_bit_set)
                ans[1] ^= it;

            else
                ans[0] ^= it;
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###