หา Element ที่ปรากฏครั้งเดียวใน Array ที่ Element อื่นปรากฏสองครั้งใน C++

โจทย์: Array มีตัวเลขทุกตัวปรากฏ 2 ครั้ง ยกเว้น 1 ตัวที่ปรากฏ 1 ครั้ง หาตัวนั้น

หลักการ: XOR properties

• x ^ x = 0
• x ^ 0 = x
• XOR associative & commutative

→ XOR ทั้ง array = ตัวที่ปรากฏครั้งเดียว

ตัวอย่างโค้ด (Python → แปลงเป็น C++)

#include <bits/stdc++.h>
using namespace std;

int singleNumber(vector<int>& nums) {
    int ans = 0;
    for (int x : nums) ans ^= x;
    return ans;
}

int main() {
    vector<int> nums = {1, 1, 5, 3, 2, 5, 2};
    cout << singleNumber(nums); // 3
}

อินพุต

[1,1,5,3,2,5,2]

เอาต์พุท

3

Complexity

• Time: O(N)
• Space: O(1)

ขยาย: หา 2 ตัวที่ปรากฏครั้งเดียว

XOR ทั้ง array → ได้ xor_all = a ^ b หา bit ที่ต่างกัน แบ่ง array เป็น 2 กลุ่ม XOR แยกกัน