Chương trình C/C++ tìm số xuất hiện số lần lẻ

Trong chương trình này chúng ta sẽ xem cách lấy một số xuất hiện số lần lẻ trong một mảng. Có nhiều cách tiếp cận khác nhau. Một trong những cách dễ nhất là thực hiện phép XOR. Nếu một số XOR với chính nó, nó sẽ bằng 0. Vì vậy nếu một số XOR chẵn lần, nó sẽ bằng 0, ngược lại là chính số đó.

Giải pháp này có một vấn đề, nếu hơn một phần tử có số lần xuất hiện lẻ, nó sẽ trả về một trong số chúng.

Thuật toán

getNumOccurredOdd(arr, n)

begin
  res := 0
  for each element e from arr, do
    res := res XOR e
  done
  return res
end

Ví dụ

#include <iostream>
using namespace std;

int getNumOccurredOdd(int arr[], int n) {
  int res = 0;
  for (int i = 0; i < n; i++)
    res = res ^ arr[i];
  return res;
}

int main() {
  int arr[] = {3, 4, 6, 5, 6, 3, 5, 4, 6, 3, 5, 5, 3};
  int n = sizeof(arr)/sizeof(arr[0]);
  cout << getNumOccurredOdd(arr, n) << " is present odd number of times";
}

Kết quả

6 is present odd number of times