[Lesson 02_2] Odd Occurences In Array

Answer

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int key=0;
    for(int i=0; i<A.size(); i++){
        key ^= A[i];
    }
    return key;
}

 

Solution Point :

이 문제의 해결 포인트는 다음과 같다.

array A의 모든 원소를 XOR 했을 때, 홀수개 인 수만 남는다.

 

XOR 테이블

입력		출력
A	B	F
0	0	0
0	1	1
1	0	1
1	1	0

XOR은 두 수가 같을 경우 0을 출력하고, 다를 경우 1을 출력한다.

즉, 동일 한 수가 두 번 나올 경우 XOR값은 0이 된다.

 

문제에 나온 예시인

9 ⊕ 3 ⊕ 9 ⊕ 3 ⊕ 9 ⊕ 7 ⊕ 9

= 1001 ⊕ 0011 ⊕ 1001 ⊕ 0011 ⊕ 1001 ⊕ 0111 ⊕ 1001

= 0111(2진수) = 7(10진수)

 

첫째자리 : 1 0 1 0 1 0 1 -> 1이 짝수개 -> 0

둘째자리 : 0 0 0 0 0 1 0 -> 1이 홀수개 -> 1

셋째자리 : 0 1 0 1 0 1 0 -> 1이 홀수개 -> 1

넷째자리 : 1 1 1 1 1 1 1 -> 1이 홀수개 -> 1

따라서 결과가 0111 즉, 7로 하나만 있는 수가 나오게 된다.