# Single Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/single-number)
Canonical: https://scaleengineer.com/dsa/problems/single-number
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Cisco](https://scaleengineer.com/companies/cisco), [Google](https://scaleengineer.com/companies/google), [Nvidia](https://scaleengineer.com/companies/nvidia), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies)
---
## Problem
Given a **non-empty** array of integers `nums`, every element appears _twice_ except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

**Example 1:**

**Input:** nums = \[2,2,1\]

**Output:** 1

**Example 2:**

**Input:** nums = \[4,1,2,1,2\]

**Output:** 4

**Example 3:**

**Input:** nums = \[1\]

**Output:** 1

**Constraints:**

* `1 <= nums.length <= 3 * 104`
* `-3 * 104 <= nums[i] <= 3 * 104`
* Each element in the array appears twice except for one element which appears only once.

# Approaches
## Brute Force Approach
This approach uses nested loops to find the single number. For each element in the array, we iterate through the entire array again to count its occurrences. If an element's count is one, it is the unique element.
**Time:** O(n^2) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** Highly inefficient with a quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' error for large inputs.
### Explanation
The brute force method is the most straightforward way to solve the problem, but also the least efficient. The core idea is to check every element and see how many times it appears in the array.

We use two nested loops. The outer loop picks an element, and the inner loop iterates through the entire array to count the occurrences of the picked element. If the count for an element is exactly one, we have found our single number and can return it immediately.

```java
public int singleNumber(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int count = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[i] == nums[j]) {
                count++;
            }
        }
        if (count == 1) {
            return nums[i];
        }
    }
    return -1; // Should not be reached given the problem constraints
}
```
### Algorithm
- 1. Iterate through the array with an outer loop from `i = 0` to `n-1`.
- 2. For each element `nums[i]`, initialize a `count` variable to 0.
- 3. Start an inner loop from `j = 0` to `n-1`.
- 4. Inside the inner loop, if `nums[i]` is equal to `nums[j]`, increment `count`.
- 5. After the inner loop finishes, check if `count` is equal to 1.
- 6. If `count` is 1, `nums[i]` is the single number. Return `nums[i]`.

## Sorting Approach
This approach involves sorting the array first. Once sorted, all duplicate elements will be adjacent to each other. We can then iterate through the sorted array to find the element that does not have an identical neighbor.
**Time:** O(n log n) · **Space:** O(log n) to O(n)
**Pros:** More efficient than the brute-force approach.; Conceptually simple after sorting.
**Cons:** Time complexity is dominated by the sorting algorithm, which is typically O(n log n), not linear.; The space complexity of sorting in-place can be O(log n) or O(n) for some algorithms, which is not constant.
### Explanation
By sorting the array, we can group identical elements together. For example, `[4,1,2,1,2]` becomes `[1,1,2,2,4]` after sorting.

After sorting, we can iterate through the array, checking elements in pairs. If `nums[i]` is not equal to `nums[i+1]`, then `nums[i]` must be the single element because its pair would have been at `nums[i+1]`. We must be careful with the boundary conditions, especially the last element, which could be the single number if all preceding elements form pairs.

```java
import java.util.Arrays;

public int singleNumber(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; i += 2) {
        if (nums[i] != nums[i+1]) {
            return nums[i];
        }
    }
    // If the loop completes, the single element is the last one
    return nums[nums.length - 1];
}
```
### Algorithm
- 1. Sort the input array `nums` in ascending order.
- 2. Iterate through the sorted array with a step of 2 (i.e., `i = 0, 2, 4, ...`).
- 3. In each iteration, compare `nums[i]` with the next element `nums[i+1]`.
- 4. If `nums[i]` is not equal to `nums[i+1]`, it means `nums[i]` is the unique element. Return `nums[i]`.
- 5. If the loop finishes without returning, it implies the single element is the last element in the array. Return `nums[nums.length - 1]`.

## Hash Set Approach
This approach uses a hash set to keep track of the elements encountered. When we see a number for the first time, we add it to the set. When we see it for the second time, we remove it. The last remaining number in the set is the single one.
**Time:** O(n) · **Space:** O(n)
**Pros:** Achieves linear time complexity, O(n).; Easy to understand the logic.
**Cons:** Requires extra space proportional to the number of unique elements, O(n) in the worst case.; Does not meet the constant space complexity requirement of the problem.
### Explanation
A hash set provides average O(1) time complexity for add, remove, and contains operations. We can leverage this to solve the problem in linear time.

We iterate through the input array. For each number, we try to add it to the set. If the number is already in the set (which `add` method can tell us by returning `false`), it means we have seen it once before, so this is its second appearance. In this case, we remove it from the set. If the number is not in the set, we add it.

After iterating through all the numbers, the hash set will contain only one element: the number that appeared an odd number of times (once, in this case).

```java
import java.util.HashSet;
import java.util.Set;

public int singleNumber(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (!set.add(num)) {
            // If add returns false, it means the element was already in the set
            set.remove(num);
        }
    }
    // The set will have only one element, which is the single number
    return set.iterator().next();
}
```
### Algorithm
- 1. Initialize an empty hash set.
- 2. Iterate through each number `num` in the input array `nums`.
- 3. Check if `num` is present in the hash set.
- 4. If it is present, remove `num` from the set.
- 5. If it is not present, add `num` to the set.
- 6. After the loop, the hash set will contain exactly one element.
- 7. Return this single element.

## Bit Manipulation (XOR) Approach
This is the most optimal approach, satisfying both linear time and constant space constraints. It leverages the properties of the XOR (exclusive OR) bitwise operator. The XOR of a number with itself is 0, and the XOR of a number with 0 is the number itself. By XORing all numbers in the array, the pairs cancel out, leaving only the single number.
**Time:** O(n) · **Space:** O(1)
**Pros:** Extremely efficient with O(n) time complexity.; Uses O(1) constant extra space.; Satisfies all problem constraints.
**Cons:** The logic might be less intuitive for those unfamiliar with bitwise operations.
### Explanation
The XOR operation has two key properties that are useful here:
  - A number XORed with itself results in 0 (e.g., `x ^ x = 0`).
  - A number XORed with 0 results in the number itself (e.g., `x ^ 0 = x`).
  - XOR is commutative and associative, meaning the order of operations doesn't matter.

We can initialize a variable, say `a`, to 0. Then, we iterate through the array and XOR each element with `a`. For any number that appears twice, say `x`, it will be XORed into the accumulator twice: `(... ^ x ... ^ x ...)`. Due to the properties of XOR, this is equivalent to `(... ^ (x ^ x) ...)` which is `(... ^ 0 ...)`. So, all the paired numbers will effectively cancel each other out.

The single number, say `y`, appears only once. It will be XORed into the accumulator once. The final result will be `0 ^ y`, which is `y`.

For example, with `nums = [4,1,2,1,2]`, the calculation would be `0 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4`.

```java
public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}
```
### Algorithm
- 1. Initialize an integer variable `result` to 0.
- 2. Iterate through each number `num` in the input array `nums`.
- 3. In each iteration, update `result` by performing a bitwise XOR with the current number: `result = result ^ num`.
- 4. After the loop completes, the value of `result` will be the single number that appears only once.
- 5. Return `result`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int SingleNumber(int[] nums) {
        return nums.Aggregate(0, (a, b) => a ^ b);
    }
}
```

### Java

```java
class Solution {
public
  int singleNumber(int[] nums) {
    int ans = 0;
    for (int v : nums) {
      ans ^= v;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var singleNumber = function (
  nums,
) {
  return nums.reduce((a, b) => a ^ b);
};

```

### CPP

```cpp
class Solution {
public:
  int singleNumber(vector<int> &nums) {
    int ans = 0;
    for (int v : nums) {
      ans ^= v;
    }
    return ans;
  }
};

```

### Python

```python
''' >>> from functools import reduce >>> reduce(lambda x, y: x ^ y, [3, 5, 3]) 5 ''' from functools import reduce class Solution : def singleNumber ( self , nums : List [ int ]) -> int : return reduce ( lambda x , y : x ^ y , nums ) ############ class Solution ( object ): def singleNumber ( self , nums ): """ :type nums: List[int] :rtype: int """ for i in range ( 1 , len ( nums )): nums [ 0 ] ^= nums [ i ] return nums [ 0 ]
```