Tìm phần tử xuất hiện một lần khi các phần tử khác xuất hiện hai lần trong C++

Cho mảng mọi phần tử xuất hiện 2 lần trừ 1 phần tử. Tìm phần tử đó.

Ví dụ

A = [1, 1, 5, 3, 2, 5, 2] → Output: 3

Giải pháp XOR

Tính chất: x ^ x = 0, x ^ 0 = x. XOR tất cả phần tử → các cặp triệt tiêu, chỉ còn phần tử đơn lẻ.

Code C++

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

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

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

Kết quả

3

Độ phức tạp: O(n) thời gian, O(1) không gian.