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

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

Giải pháp này có một vấn đề, nếu nhiều 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";
}

Đầu ra

6 is present odd number of times