# (草稿版)LeetCode Single Number
###### tags: `leetcode`、`Math`
---

## Description

- Given a non-empty array of integers, every element appears twice except for one. Find that single one.

- 中文翻譯：給定一個整數陣列，陣列中只有一種元素只出現過一次，剩下其他種的元素都出現二次。找出那個只出現過一次的元素

---

## Propositions
- 只有一種元素的出現次數為1
- 除了第一項提到的元素之外，剩餘元素的出現次數為2
- 我們要找出只出現一次的元素

---

## XOR operation
- 當xor要計算相同元素時，會輸出為0；反之，計算不同元素時，會輸出為1的元素
- xor 具有交換性，換言之，運算元任意被調換位置並不會改變結果，比如A xor B xor C = A xor C xor B = B xor C xor A
- 0 xor A = A，A為任意元素

---

## XOR example 1

2 xor 2 xor 1 -> 0 xor 1

---

## XOR example 2


4 xor 1 xor 2 xor 1 xor 2 -> 1 xor 1 xor 2 xor 2 xor 4

---

## XOR example 2 (cont'd)


---

## XOR example 3
如果我們將式子推廣至 (N+1)個元素的整數陣列

---

## Algorithm

---

## Implement in C


---

## Performance

- Time complexity: O(n), 由於執行時間會隨資料大小來線性成長，所以為n
- Space complexity: O(1), 由於空間並不會隨資料大小而成長，所以為1

## 編輯進度

2020/07/15 增加並修改解法和效能的說明
2020/07/14 完成初步的編輯

## 編輯目標

1. 訓練自己以純粹不添加其他程式語言特性來思考解法
2. 每隔一段時間來重新審定文章並修改