Find the odd int

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).

 

Solution

#include <vector>
#include <map>

int findOdd(const std::vector<int> &numbers) {
  std::map<int, bool> table;

  for (auto x : numbers) {
    table[x] = !table[x];
  }

  for (auto x : numbers) {
    if (table[x] == true) return x;
  }

  exit(1);
}

 

lucianmusat의 코드

#include <vector>

int findOdd(const std::vector<int>& numbers){
  for (auto elem: numbers){
    if (std::count(numbers.begin(), numbers.end(), elem) % 2 != 0) {
      return elem;
    }
  }
  return 0;
}

 

Unnamed의 코드

#include <functional>
#include <numeric>
#include <vector>

int findOdd(const std::vector<int>& numbers) {
  return std::accumulate(numbers.cbegin(), numbers.cend(), 0, std::bit_xor<>());
}

 

DJHenjin의 코드

#include <vector>

int findOdd(const std::vector<int>& numbers){
  int result = 0;
  for(auto& num : numbers){
    result = result ^ num;    
  }
  return result;
}

 

Unnamed의 코드

#include <functional>
#include <numeric>
#include <vector>

int findOdd(const std::vector<int>& numbers) {
  return std::reduce(numbers.cbegin(), numbers.cend(), 0, std::bit_xor<>());
}

 

후기

이 짧은 CodeKata에 정말 다양한 풀이법이 있다. STL은 그렇다 치고, XOR 비트 연산자 ^가 탐난다. 이런 걸 나는 ! 연산자로 바꿔가는 걸 했다니. 앞으로는 XOR를 사용하도록 해봐야겠다. 솔직히 좀 부럽기도 하다. 나는 모르는 걸 저 사람들은 어떻게 알고 저렇게 아름답게 풀어낼 수 있는 것일까.

 

(url: https://www.codewars.com/kata/54da5a58ea159efa38000836)