Single Number III ใน C++

ให้อาร์เรย์มีตัวเลขทุกตัวปรากฏ 2 ครั้ง ยกเว้น 2 ตัวที่ปรากฏ 1 ครั้ง หาทั้งสองตัวนั้น

ตัวอย่าง: [1,2,3,1,5,2] → [3,5]

ขั้นตอนการแก้ปัญหา (XOR + Bit Partition)

1. XOR ทั้งอาร์เรย์ → xor_all = a ^ b (a,b คือตัวที่ไม่ซ้ำ)
2. หาบิตที่ต่างกัน (LSB ที่เป็น 1): pos = __builtin_ctz(xor_all) หรือวนลูปหา
3. แบ่งอาร์เรย์เป็น 2 กลุ่มตามบิต pos:
   • กลุ่ม 1: บิต pos = 1 → XOR ได้ a
   • กลุ่ม 2: บิต pos = 0 → XOR ได้ b
4. คืน [a, b]

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

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

void print_vector(vector<int> v) {
    cout << "[";
    for (int x : v) cout << x << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xor_all = 0;
        for (int x : nums) xor_all ^= x;
        int pos = 0;
        while ((xor_all & (1 << pos)) == 0) pos++;
        int a = 0;
        for (int x : nums) if (x & (1 << pos)) a ^= x;
        int b = xor_all ^ a;
        return {a, b};
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,1,3,2,5};
    print_vector(ob.singleNumber(v));
}

Input

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

Output

[3, 5, ]