Hiểu bài toán

Bài toán yêu cầu tìm giá trị duy nhất trong một dãy số có độ dài lẻ n, trong đó mọi số khác đều xuất hiện đúng 2 lần (tần suất chẵn), chỉ có một số xuất hiện với tần suất lẻ (có thể là 1 lần, 3 lần...). Do độ dài dãy là số lẻ, số này chắc chắn tồn tại.

Các cách tiếp cận

Cách Hash Map (Sử dụng map)

#include <iostream>
#include <map>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    map<int, int> mp;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        mp[x]++;
    }

    for (auto p : mp) {
        if (p.second % 2 != 0) {
            cout << p.first << endl;
            break;
        }
    }

    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Sử dụng một map (hoặc hash map) để đếm tần suất xuất hiện của từng số. Sau khi nhập xong toàn bộ dãy, duyệt qua map và tìm số nào có tần suất lẻ. Do sử dụng map (cây đỏ-đen), thời gian chèn và tìm kiếm mỗi phần tử là O(log n), tổng thời gian là O(n log n).

Cách Bitwise XOR (Phép toán XOR)

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int result = 0;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        result ^= x;
    }

    cout << result << endl;

    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Tận dụng tính chất của phép toán XOR (khoảng loại): a ^ a = 0 và a ^ 0 = a. Vì mọi số xuất hiện chẵn lần sẽ triệt tiêu lẫn nhau (tổng XOR về 0), số còn lại sau khi XOR toàn bộ dãy chính là số xuất hiện lẻ lần. Ví dụ: 1 ^ 2 ^ 2 ^ 3 ^ 1 = (1^1) ^ (2^2) ^ 3 = 0 ^ 0 ^ 3 = 3.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Phép toán XOR có tính chất 'khoảng loại' (a ^ a = 0), rất phù hợp để giải quyết bài toán tìm số xuất hiện lẻ lần khi các số khác xuất hiện chẵn lần.
• Bài toán có thể được giải quyết trong thời gian tuyến tính O(n) và không gian hằng O(1) bằng cách sử dụng XOR thay vì dùng thêm bộ nhớ đếm tần suất.

Lỗi thường gặp

• Nếu dùng map để đếm, cần lưu ý độ phức tạp thời gian O(n log n) có thể sát sao giới hạn nếu n rất lớn (10^6), mặc dù vẫn đủ thời gian chạy trong hầu hết trường hợp.
• Cần đảm bảo biến lưu kết quả ban đầu được khởi tạo đúng (0 cho XOR) và kiểu dữ liệu đủ chứa giá trị đầu vào (dùng int hoặc long long tùy theo giới hạn a_i).