[ Codility ] - Lesson2 OddOccurrencesInArray(C++)

문제조건

• 값이 정의된 벡터 A
• xor

문제풀이

int solution(vector<int> &A) {
    int sum = 0;

    for(int i = 0; i < A.size(); i++)
    {
        sum ^= A[i];
    }

    return sum;
}

코드설명

  xor의 특징은 같은 값을 더하면 0이 됩니다. 이 것을 이용하여 같은 값이 나오면 0이고 짝이 지어지지 않은 남은 값이 어떤 것인지 알 수 있습니다.

ex) 1⊕2⊕1⊕5⊕2
= (1⊕1)⊕(2⊕2)⊕5
= 0 ⊕ 0 ⊕ 5 = 5

그리고 다음은 코딩테스트 할 때, 알아두면 좋은 xor의 특징입니다

• A ^ B ^ B == A
• A ^ A == 0
• if (A ^ B == C), (C ^ A == B) and (C ^ B == A)

결과사진