โปรแกรม C/C++ หาจำนวนครั้งคี่?

ในโปรแกรมนี้ เราจะมาดูกันว่าเราจะหาตัวเลขที่เกิดขึ้นเป็นจำนวนคี่ในอาร์เรย์ได้อย่างไร มีหลายวิธีที่แตกต่างกัน วิธีที่ง่ายที่สุดวิธีหนึ่งคือการดำเนินการ ZOR ถ้าตัวเลข XORed กับตัวเอง มันจะเป็น 0 ดังนั้นถ้า XORed จำนวนคู่ มันจะเป็น 0 มิฉะนั้น ตัวเลขนั้นเอง

วิธีแก้ปัญหานี้มีปัญหาหนึ่งข้อ หากองค์ประกอบมากกว่าหนึ่งรายการมีจำนวนครั้งคี่ องค์ประกอบจะส่งคืนหนึ่งในองค์ประกอบนั้น

อัลกอริทึม

getNumOccurredOdd(arr, n)

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

ตัวอย่าง

#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";
}

ผลลัพธ์

6 is present odd number of times