[Codility/Java] 문제 3. OddOccurrencesInArray

OddOccurrencesInArray

 

Task

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.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

• the elements at indexes 0 and 2 have value 9,
• the elements at indexes 1 and 3 have value 3,
• the elements at indexes 4 and 6 have value 9,
• the element at index 5 has value 7 and is unpaired.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

• N is an odd integer within the range [1..1,000,000];
• each element of array A is an integer within the range [1..1,000,000,000];
• all but one of the values in A occur an even number of times.

 

Solution

class Solution {
    public int solution(int[] A) {
        int result = 0;

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

        return result;
    }
}

 

Notion

XOR 비트연산(^)

: 대응되는 비트가 서로 다른 경우, 1을 반환함.

 

즉, 이번 문제에서 같은 숫자를 xor 연산하게 되면 모두 0000의 비트를 반환하게 되고, 이를 마지막 남은 짝이 없는 숫자와 xor 연산을 하면 결국 남은 숫자가 return 되게 된다.

 

사실 이 문제는 답을 떠올리지 못해서 해설을 검색해서 풀었다.

HashMap을 활용해 푼 사람들도 있었는데 시간복잡도면에서 가장 효율이 좋은 xor 알고리즘으로 풀어보았다. 답을 보면서도 이런 생각을 문제를 보자마자 어떻게 떠올렸을까 싶었다.

연습만이 살길! 열심히 해보자.