# Single Number III
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/single-number-iii)
Canonical: https://scaleengineer.com/dsa/problems/single-number-iii
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## Problem
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.

**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:** [1,0]

**Constraints:**

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

# Approaches
## Using HashMap
Use a HashMap to store the frequency of each number in the array. Then iterate through the HashMap to find the two numbers with frequency 1.
**Time:** O(n) where n is the length of the input array · **Space:** O(n) to store the HashMap
**Pros:** Easy to understand and implement; Works for any range of numbers
**Cons:** Does not meet the constant space requirement; Requires extra space proportional to input size
### Explanation
This approach uses a HashMap to keep track of the frequency of each number in the array. We first iterate through the array and store the count of each number in the HashMap. Then, we iterate through the HashMap to find the two numbers that appear only once (frequency = 1).

```java
public int[] singleNumber(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    
    // Count frequency of each number
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    
    int[] result = new int[2];
    int index = 0;
    
    // Find numbers with frequency 1
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (entry.getValue() == 1) {
            result[index++] = entry.getKey();
        }
    }
    
    return result;
}
```
### Algorithm
1. Create a HashMap to store number-frequency pairs
2. Iterate through the array and count frequency of each number
3. Iterate through the HashMap
4. Find numbers with frequency 1 and add them to result array
5. Return the result array

## Using XOR and Bit Manipulation
Use XOR operation to find the two unique numbers by first getting their XOR, then separating them based on a set bit in their XOR result.
**Time:** O(n) where n is the length of the input array · **Space:** O(1) as it uses only a constant amount of extra space
**Pros:** Meets the linear time complexity requirement; Uses constant extra space; Efficient bit manipulation solution
**Cons:** Requires understanding of bit manipulation; May be less intuitive than other approaches
### Explanation
This approach uses the properties of XOR operation. When we XOR all numbers, we get the XOR of the two unique numbers (as all other numbers appear twice and get cancelled). Then, we find a set bit in this XOR result (as the two numbers are different, they must differ in at least one bit). We use this bit to divide all numbers into two groups, and XOR numbers in each group separately to get our two unique numbers.

```java
public int[] singleNumber(int[] nums) {
    // Get XOR of all numbers
    int xorResult = 0;
    for (int num : nums) {
        xorResult ^= num;
    }
    
    // Find rightmost set bit in xorResult
    int rightmostSetBit = 1;
    while ((xorResult & rightmostSetBit) == 0) {
        rightmostSetBit <<= 1;
    }
    
    // Divide numbers into two groups and XOR
    int x = 0, y = 0;
    for (int num : nums) {
        if ((num & rightmostSetBit) != 0) {
            x ^= num;
        } else {
            y ^= num;
        }
    }
    
    return new int[]{x, y};
}
```
### Algorithm
1. XOR all numbers to get XOR of two unique numbers
2. Find rightmost set bit in the XOR result
3. Use this bit to divide numbers into two groups
4. XOR numbers in each group separately
5. Return the two resulting numbers

# Solutions
### CSharp

```csharp
public class Solution {
    public int[] SingleNumber(int[] nums) {
        int xs = nums.Aggregate(0, (a, b) => a ^ b);
        int lb = xs & -xs;
        int a = 0;
        foreach(int x in nums) {
            if ((x & lb) != 0) {
                a ^= x;
            }
        }
        int b = xs ^ a;
        return new int[] {
            a,
            b
        };
    }
}
```

### Java

```java
class Solution { public int [] singleNumber ( int [] nums ) { int xs = 0 ; for ( int x : nums ) { xs ^= x ; } int lb = xs & - xs ; int a = 0 ; for ( int x : nums ) { if (( x & lb ) != 0 ) { a ^= x ; } } int b = xs ^ a ; return new int [] { a , b }; } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number[]} */ var singleNumber =
  function (nums) {
    const xs = nums.reduce((a, b) => a ^ b);
    const lb = xs & -xs;
    let a = 0;
    for (const x of nums) {
      if (x & lb) {
        a ^= x;
      }
    }
    const b = xs ^ a;
    return [a, b];
  };

```

### Python

```python
def lowbit ( x ): return x & ( - x ) # Example usage number = 12 # Binary: 1100 print ( lowbit ( number )) # Output: 4 (Binary: 100) number = 10 # Binary: 1010 print ( lowbit ( number )) # Output: 2 (Binary: 10) number = 18 # Binary: 10010 print ( lowbit ( number )) # Output: 2 (Binary: 10)
```

### CPP

```cpp
class Solution { public: vector < int > singleNumber ( vector < int >& nums ) { long long xs = 0 ; for ( int & x : nums ) { xs ^= x ; } int lb = xs & - xs ; int a = 0 ; for ( int & x : nums ) { if ( x & lb ) { a ^= x ; } } int b = xs ^ a ; return { a , b }; } };
```