[Codility] OddOccurencesInArray

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired. Returns the value of the unpaired element

 

문제를 풀기에 앞서 간단히 생각할 수 있는 방법은 이중 for문으로 O(n^2) 탐색이 있습니다. 

하지만, XOR의 동일값 제거 특성을 이용한다면 O(N)의 시간 복잡도로 문제를 풀 수 있습니다.

 

XOR 비트 연산은 여러개의 수가 있을때, 

1001 ^ 1111 ^ 1001 = 1111 과 같이 동일한 값은 의미 없어지고 Pair가 없는 하나의 수만 남는 연산 특성이 있습니다.

연산 순서가 바뀌어도 결과값은 동일합니다.

 

또한 시작값을 0으로 하게되면 0 ^ X = X 이므로 A[0] 의 값을 result에 저장해 A[A.length-1]까지 모두 비교해 볼 수 있습니다.

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int result = 0;
        
        for(int i=0; i<A.length; i++){
            result ^= A[i];
        }
        
        return result;
    }
}