[136]SingleNumber

 

leetcode.com/problems/single-number/

---

두 가지 이유로 XOR을 통해 해결할 수 있습니다.

 

1. XOR은 결합법칙과, 교환법칙이 성립합니다.

2. 자기 자신과의 XOR 결과는 0 입니다. 10^10 = 0, A^A = 0

 

주어진 리스트의 1개를 제외하고는 모두 2개라는 성질을 이용하면

 

ABCDEDCBA

 

위 예시 숫자를 교환법칙을 사용해서 두 쌍씩 괄호로 묶어줍니다. (AA)(BB)(CC)(DD)E

 

여기에 XOR을 하게 되면 결국 0 ^ E 만 남게 되어 하나짜리 E만 남는 형태입니다.

---

public int singleNumber(int[] nums) {
    int xorResult = 0;
    for (int i = 0; i < nums.length; ++i)
    {
        xorResult = xorResult ^ nums[i];
    }
    return xorResult;
}