> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/bit-manipulation/xor/single-number.md).

# Single Number

https\://leetcode.com/problems/single-number/description/

> Given an array of integers, every element appears twice except for one. Find that single one.
>
> Note:
>
> Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

## Thoughts

A XOR A == 0, A XOR B XOR A = B.

## Code

```
class Solution {
    public int singleNumber(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res = res ^ nums[i];
        }
        return res;
    }
}
```

## Analysis

时间复杂度O(n), 空间O(1).