[LeetCode] 136. Single Number

轉自LeetCode

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?

<Solution>
這題本身不難，但是因為要求 O(N) 以及不能使用額外的空間，很難直接想到解法

其實這題是在考 XOR 的觀念

S 是要找的答案

N1 ^ N1 ^ N2 ^ N2 ..... ^ Nx ^ Nx ^ S

= (N1 ^ N1) ^ ( N2 ^ N2) .... ^ (Nx ^ Nx) ^ S

= 0 ^ 0 .... ^ 0 ^ S

= S

所以只要用 XOR 歷遍一次，答案就出來了

code 如下(參考資料)
c++

Kotlin