# LeetCode - Single Number III

## Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/single-number-iii

Example 1:

``````Input: nums = [1, 2, 1, 3, 2, 5]
Output: [3, 5]
Explanation:  [5, 3] is also a valid answer.
``````

Example 2:

``````Input: nums = [-1, 0]
Output: [-1, 0]
``````

Example 3:

``````Input: nums = [0, 1]
Output: [0, 1]
``````

Constraints:

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

### Explanation

#### Sorting

We sort the array elements and compare the adjacent elements. We can easily get the non-repeating element using the above approach.

A C++ snippet of the above approach is as below:

``````sort(nums, nums + n);
vector<int> result;

for (int i = 0; i < n - 1; i = i + 2) {
if (nums[i] != nums[i + 1]) {
result.push_back(nums[i]);
i = i - 1;
}
}

if (result.size() == 1)
result.push_back(nums[n - 1]);

return result;``````

The time complexity of the program is O(nlog(n)), and the space complexity is O(1).

#### HashMap

The problem can be solved in O(n) using a HashMap. We run a loop over the array and count the number of occurrences of each element in the array.

We iterate over the hash and print the two numbers that appeared only once.

A C++ snippet of the above approach is as below:

``````int n = nums.size();
vector<int> result;

if(n == 0) {
return result;
}

map<int, int> m;

for(int i = 0; i < n; i++) {
m[nums[i]]++;
}

vector<int> result;

for(auto i = m.begin(); i != m.end(); i++) {
if(i->second == 1) {
result.push_back(i->first);
}
}

return result;``````

The time complexity of the program is O(n), and the space complexity is O(n).

#### XOR operator

The program can be solve in O(n) time complexity and O(1) space complexity using XOR operation.

Let a and b be the elements that appears exactly once in nums array. We first compute the XOR of all the array elements.

``xor = nums[0]^nums[1]^nums[2]....nums[n - 1]``

All the bits that are set in the above xor variable will be set in one non-repeating element either a or b.

We take the any set bit of xor and divide the elements of the array in two sets. One set of elements with same bit set and another with the same bit not set.

We do XOR of all the elements in the first set which will return the first non-repeating element, and doing the same in another set will return the second non-repeating element.

Let's check the algorithm first.

``````- set xorResult = nums[0]
a = 0, b = 0, i = 0
vector<int> result

- loop for i = 1; i < nums.size(); i++
- xorResult ^= nums[i]

- set setBitNo = xorResult == INT_MIN ? 0 : xorResult & ~(xorResult - 1)

- loop for i = 0; i < nums.size(); i+=
- if nums[i] & setBitNo
- a ^= nums[i]
- else
- b ^= nums[i]

- result.push_back(a)
- result.push_back(b)

- return result
``````

The time complexity of the above approach is O(n), and the space complexity is O(1).

Let's check our algorithm in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int xorResult = nums[0];
int a = 0, b = 0, i;
vector<int> result;

for(i = 1; i < nums.size(); i++) {
xorResult ^= nums[i];
}

int setBitNo = xorResult == INT_MIN ? 0 : xorResult & ~(xorResult - 1);

for(i = 0; i < nums.size(); i++) {
if(nums[i] & setBitNo) {
a ^= nums[i];
} else {
b ^= nums[i];
}
}

result.push_back(a);
result.push_back(b);
return result;
}
};``````

#### Golang solution

``````func singleNumber(nums []int) []int {
xorResult := 0

for _, num := range nums {
xorResult = xorResult ^ num
}

setBitNo := xorResult & (-xorResult)

result := make([]int, 2)

for _, num := range nums {
if num & setBitNo == 0 {
result[0] ^= num
} else {
result[1] ^= num
}
}

return result
}``````

#### Javascript solution

``````var singleNumber = function(nums) {
let xorResult = 0;
let a = 0, b = 0, i = 0;

for(i = 0; i < nums.length; i++){
xorResult ^= nums[i];
}

let setBitNo = xorResult & ~(xorResult - 1);

for(i = 0; i < nums.length; i++) {
if((nums[i] & setBitNo) === 0)
a ^= nums[i];
else
b ^= nums[i];
}

return [a, b];
};``````

#### Dry Run

Let's dry-run our algorithm for Example 1.

``````Input: nums = [1, 2, 1, 3, 2, 5]

Step 1: xorResult = nums[0]
= 1

Step 2: int a = 0, b = 0, i
vector<int> result

Step 3: loop for i = 1; i < nums.size(); i++
xorResult ^= nums[i]

The xorResult is 6 (0110)

Step 4: setBitNo = xorResult == INT_MIN ? 0 : xorResult & ~(xorResult - 1)
= 6 == INT_MIN ? 0 : xorResult & ~(xorResult - 1)
= false ? 0 : xorResult & ~(xorResult - 1)
= xorResult & ~(xorResult - 1)
= 6 & ~(6 - 1)
= 6 & ~5
= 6 & -6
= 2

Step 5: loop for i = 0; i < nums.size()
0 < 6
true

if nums[i] & setBitNo
nums[0] & 2
1 & 2
0001 & 0010
0
false
else
b ^= nums[i]
= b ^ nums[i]
= 0 ^ nums[0]
= 0 ^ 1
= 1
i++
i = 1

Step 6: loop i < nums.size()
1 < 6
true

if nums[i] & setBitNo
nums[1] & 2
2 & 2
0010 & 0010
2
true
a ^= nums[i]
= a ^ nums[1]
= 0 ^ 2
= 2

i++
i = 2

Step 7: loop i < nums.size()
2 < 6
true

if nums[i] & setBitNo
nums[2] & 2
1 & 2
0001 & 0010
0
false
else
b ^= nums[i]
= b ^ nums[i]
= 1 ^ nums[2]
= 1 ^ 1
= 0
i++
i = 3

Step 8: loop i < nums.size()
3 < 6
true

if nums[i] & setBitNo
nums[3] & 2
3 & 2
0011 & 0010
2
true
a ^= nums[i]
= a ^ nums[3]
= 2 ^ 3
= 1

i++
i = 4

Step 9: loop i < nums.size()
4 < 6
true

if nums[i] & setBitNo
nums[4] & 2
2 & 2
0010 & 0010
2
true
a ^= nums[i]
= a ^ nums[4]
= 1 ^ 2
= 3

i++
i = 5

Step 10: loop i < nums.size()
5 < 6
true

if nums[i] & setBitNo
nums[5] & 2
5 & 2
0101 & 0010
0
false
else
b ^= nums[i]
= b ^ nums[i]
= 0 ^ nums[5]
= 0 ^ 5
= 5

i++
i = 6

Step 11: loop i < nums.size()
6 < 6
false

Step 12: result.push_back(a)
result.push_back(3)
result = [3]

result.push_back(b)
result.push_back(5)
result = [3, 5]

return result

We return the result as [3, 5]
``````
Share this post!