Hiểu bài toán

Bài toán yêu cầu tìm một số bị thiếu trong một dãy số nguyên. Dãy số ban đầu chứa tất cả các số nguyên từ 1 đến n, nhưng một số đã bị xóa. Đầu vào cung cấp n và dãy số còn lại (có độ dài n-1). Đầu ra là số bị thiếu.

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

Cách Hash Set (Tập hợp)

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

int main () {
    int n;
    cin >> n;
    set<int> s;
    for (int i = 0; i < n - 1; i++){
        int x;
        cin >> x;
        s.insert(x);
    }
    for (int i = 1; i <= n; i++){
        if (s.find(i) == s.end()){
            cout << i;
            break;
        }
    }
    return 0;
}

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

Phương pháp này sử dụng một cấu trúc dữ liệu tập hợp (set) để lưu trữ các số có trong đầu vào. Sau đó, ta chỉ cần duyệt từ 1 đến n và kiểm tra số nào không có trong tập hợp đó. Vì độ phức tạp của thao tác chèn và tìm kiếm trong set là O(log n), nên độ phức tạp tổng thể là O(n log n).

Cách Công thức tổng quát (Summation)

#include <bits/stdc++.h>
using namespace std;
long long n, sum_input = 0;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (long long i = 0; i < n - 1; i++){
        long long x;
        cin >> x;
        sum_input += x;
    }
    long long sum_all = n * (n + 1) / 2;
    cout << sum_all - sum_input << endl;
    return 0;
}

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

Đây là phương pháp tối ưu nhất. Ta biết rằng tổng của các số từ 1 đến n là n*(n+1)/2. Bằng cách tính tổng các số có sẵn trong đầu vào và trừ đi từ tổng lý thuyết, ta thu được số còn thiếu. Phương pháp này chạy trong thời gian tuyến tính O(n) và chỉ cần bộ nhớ hằng định O(1).

Cách Phép toán XOR (Bit Manipulation)

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

int main() {
    int n;
    cin >> n;
    int xor_all = 0;
    int xor_input = 0;

    // XOR all numbers from 1 to n
    for (int i = 1; i <= n; i++) {
        xor_all ^= i;
    }

    // XOR all input numbers
    for (int i = 0; i < n - 1; i++) {
        int x;
        cin >> x;
        xor_input ^= x;
    }

    // The missing number is the result
    cout << (xor_all ^ xor_input);
    return 0;
}

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

Sử dụng tính chất của phép toán XOR: a XOR a = 0. Nếu ta XOR tất cả các số từ 1 đến n và XOR tất cả các số trong dãy bị thiếu, các số xuất hiện 2 lần sẽ triệt tiêu nhau, chỉ còn lại số bị thiếu. Phương pháp này cũng có độ phức tạp O(n) và O(1) bộ nhớ, và không lo về việc tràn số (integer overflow) như phương pháp cộng trừ.

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

Bài học kinh nghiệm

• Bài toán có thể được giải quyết bằng nhiều cách: sử dụng cấu trúc dữ liệu, tính tổng, hoặc phép toán bitwise.
• Phương pháp tính tổng (Summation) và XOR là tối ưu nhất về thời gian (O(n)) và bộ nhớ (O(1)).

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow): Khi n lớn (ví dụ 10^6), tổng n*(n+1)/2 có thể vượt quá giới hạn của kiểu int 32-bit. Cần sử dụng kiểu long long.
• Độ dài đầu vào: Chỉ có n-1 số cần đọc, không đọc thừa.