被りのない数字を一つだけ取り出す

問題

Example:
Input: [4, 3, 2, 4, 1, 3, 2]
Output: 1
Here's the function signature:

def singleNumber(nums):
# Fill this in.

print singleNumber([4, 3, 2, 4, 1, 3, 2])

一つだけ2回出現しない数字のリストを与えられて、一つの数値を見つける関数
ただし使えるメモリはO(1)である

例:
Input: [4, 3, 2, 4, 1, 3, 2]
Output: 1

.
.
.
.
.
.
.

回答

O(1)で回答しなければいけないためマップを作って重複チェックは使えない。O(N)使うことになるため。
計算量O(N^2)なら計算はできそうだが、もう少し良い方法を考えたい。

XORを使えばいい感じにできそうだ

同じ数のXORは必ずゼロになる例えば 4^4
またXORは交換法則があるため

4 ^ 3 ^ 2 ^ 4 ^ 1 ^ 3 ^ 2 = 1 ^ 4 ^ 4 ^ 3 ^ 3 ^ 2 ^ 2


と変換出来る
これを変換して行くと最終的に

1 ^ 0 = 1

となり1を抽出できる

コード

function singleNumber(nums){
    let sum = nums[0]
    for(let i = 1; i < nums.length; i++){
        sum ^= nums[i] 
    }

    return sum
}

ちょっと難しかった