[Codewars] Find the odd int (6 kyu) / JavaScript

https://www.codewars.com/kata/54da5a58ea159efa38000836/javascript

Codewars - Achieve mastery through coding practice and developer mentorship

 

DESCRIPTION:

Given an array of integers, find the one that appears an odd number of times.

There will always be only one integer that appears an odd number of times.

 

Examples

[7] should return 7, because it occurs 1 time (which is odd).
[0] should return 0, because it occurs 1 time (which is odd).
[1,1,2] should return 2, because it occurs 1 time (which is odd).
[0,1,0,1,0] should return 0, because it occurs 3 times (which is odd).
[1,2,2,3,3,3,4,3,3,3,2,2,1] should return 4, because it appears 1 time (which is odd).

 

설명:

정수의 배열이 주어지면 홀수번 나타나는 정수를 찾습니다.

홀수번 나타나는 정수는 항상 하나뿐입니다.

 

예시

[7]은 7이 1번 나타나기 때문에(홀수) 7을 반환하여야 합니다.
[0]은 0이 1번 나타나기 때문에(홀수) 0을 반환하여야 합니다.
[1,1,2]은 2가 1번 나타나기 때문에(홀수) 2를 반환하여야 합니다.
[0,1,0,1,0]은 0이 3번 나타나기 때문에(홀수) 0을 반환하여야 합니다.
[1,2,2,3,3,3,4,3,3,3,2,2,1]은 4가 1번 나타나기 때문에(홀수) 4를 반환하여야 합니다.

 

풀이

function findOdd(A) {
  let set = [...new Set(A)];
  for(let i = 0; i < set.length; i++){
    let count = 0;
    for(let j = 0; j < A.length; j++){
      if(set[i] === A[j]) count++;
    }
    if(count % 2 === 1) return set[i];
  }
}

입력받은 배열 A의 원소를 set를 이용해 중복 없이 담아서 이중 반복문으로 set에 있는 원소가 A에 있는 원소와 같을 때 count를 하나씩 늘리고 안쪽 반복문을 나왔을 때 count가 홀수라면 그 set의 값을 반환한다.

 

다른 사람의 좋았던 풀이

const findOdd = (xs) => xs.reduce((a, b) => a ^ b);

XOR 연산자를 이용해서 풀었다. XOR 연산은 비트 별로 수행될 때 비트가 같으면 0을 반환하고 비트가 다르면 1을 반환한다.

0 ^ 0	0
0 ^ 1	1
1 ^ 0	1
1 ^ 1	0

정수 5와 1을 XOR 연산으로 실행했을 때 피연산자는 32비트 정수로 변환되고 다음과 같이 계산된다.

5	00000000000000000000000000000101
1	00000000000000000000000000000001
5 ^ 1	00000000000000000000000000000100 (4)

만약 같은 정수가 더해진다면 모든 비트가 같기 때문에 XOR 연산의 결과는 0이 된다. 그러므로 정수를 짝수번 더한다면 XOR 연산을 했을 경우 0이 된다는 점을 알 수 있다. 그래서 reduce를 이용하여 모든 수를 XOR 연산을 한다면 홀수번 등장하는 수만 남는다는 것을 이용한 풀이이다.

 

참고

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_XOR

Bitwise XOR (^) - JavaScript | MDN

https://www.w3schools.com/js/js_bitwise.asp

JavaScript Bitwise