[Codility] OddOccurrencesInArray

문제설명

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:

function solution(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.

풀이

function solution(A) {
  let result = 0;
  for (let i = 0; i < A.length; i++) {
    result = result ^ A[i];
  }
  return result
}

첫 번째 풀이에서는 for()에다가 filter()를 사용했다.
runtime Error 뿐만 아니라 timeout Error도 발생했다.
시간복잡도가 O(N**2) 였다.

결국 내가 생각한 시간을 넘겨서 해답을 찾아보던 중 XOR 연산을 하는 해답을 보게 됐다.
사실 해답도 처음에는 제대로 이해가 되지 않았다.

XOR 연산

0과 1을 비교할 때 두 수가 다를 때만 1을 반환한다.
같은 수를 XOR 연산하게 되면 0을 반환하게 된다.

console.log(9 ^ 9); // 0

이 내용을 이용해서 결론적으로 1개의 다른 수만 찾으면 되기 때문에 모든 수를 XOR 연산하게 되면 해당 수만 나오게 된다.

console.log(9 ^ 3 ^ 6 ^ 3 ^ 9 ^ 7); // 7

앞으로 시간복잡도 계산도 할 줄 알아야 될 거 같다.
코딜리티를 통해서 매우 겸손해지고 있는 요즘이다..😞