โปรแกรม C/C++ หาตัวเลขที่เกิดขึ้นเป็นจำนวนครั้งคี่

ในโปรแกรมนี้ เราจะดูวิธาหาตัวเลขที่เกิดขึ้นเป็นจำนวนครั้งคี่ (Odd number of times) ในอาร์เรย์ มีหลายวิธี วิธีง่ายที่สุดคือใช้ XOR ถ้าตัวเลข XOR กับตัวเอง จะได้ 0 ถ้า XOR จำนวนคู่ครั้ง = 0 จำนวนคี่ครั้ง = ตัวเลขนั้นเอง

ข้อจำกัด: ถ้ามีหลายตัวที่เกิดขึ้นเป็นจำนวนคี่ครั้ง จะคืนค่าเพียงตัวเดียว

อัลกอริทึม

getNumOccurredOdd(arr, n)

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

ตัวอย่างโค้ด (C++)

#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