Codility OddOccurrencesInArray JavaScript 풀이

https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

OddOccurrencesInArray coding task - Learn to Code - Codility

내가 처음 제출한 코드는 아래와 같다.

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    A.sort();
    
    var result;
    
    A.reduce((acc, cur) => {
        if (A.indexOf(acc) % 2 === 0 && acc !== cur) {
            result = acc;
            return cur;
        } else {
            return cur;
        }
    });
    
    return result;
}

테스트 케이스는 통과했지만, 스코어는 33%를 기록했기 때문에 정확한 풀이는 아니다.

 

또, 너무 복잡한 방식으로 푼 거 같아 다른 풀이들은 찾아봤는데 XOR 연산과 관련된 내용이 많이 나왔다.

그 중, 참고한 것은

https://gist.github.com/k0ff33/3eb60cfb976dee0a0a969fc9f84ae145

Odd Occurrences In Array exercise from Codility (JavaScript/NodeJS)

이 분이 작성하신 function solution(A)인데

처음엔, 이 코드를 보아도 XOR 연산이 어떻게 이 문제의 해결 방법인지 이해가 되질 않았다.

 

생각해보니

[9, 3, 7, 3, 6, 9, 7] 이 배열을 예로 들면,

연산되는 것은 9 ^ 3 ^ 7 ^ 3 ^ 6 ^ 9 ^ 7이다.

이는 (9 ^ 9) ^ (3 ^ 3) ^ (7 ^ 7) ^ 6과 같이 바꿀 수 있다.

이는 같은 수끼리의 XOR 연산은 0이므로 0 ^ 0 ^ 0 ^ 6이 되고

0 ^ 0 = 0, 0 ^ n 이므로 결과는 6이 된다.

 

같은 수끼리의 XOR 연산이 0이 되는 이유와 0 ^ 0 = 0, 0 ^ n = n이 되는 이유를 혹시 모른다면,

비트 연산을 공부해보는 것이 좋다.

 

최종 제출한 코드는 다음과 같다.

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    return A.reduce((arr, cur) => {
        return arr ^= cur;
    });
}