Hiểu bài toán

Bài toán yêu cầu tìm số duy nhất bị thiếu trong một dãy gồm n số nguyên dương. Dãy này chứa các số trong khoảng từ 1 đến n+1, nhưng chỉ có n số (thiếu đúng 1 số). Ta cần xác định số nào bị thiếu đó.

Ví dụ: Với n=4 và dãy [1, 5, 4, 3], các số từ 1 đến 5 là {1, 2, 3, 4, 5}. Dãy input có {1, 3, 4, 5}, thiếu số 2.

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

Cách Phép tính tổng

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;
    cin >> n;
    long long total_sum = (long long)(n + 1) * (n + 2) / 2;
    long long array_sum = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        array_sum += x;
    }

    cout << total_sum - array_sum;
    return 0;
}

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

Cách tiếp cận này dựa trên phép tính tổng. Tổng các số từ 1 đến n+1 là (n+1)(n+2)/2. Nếu ta lấy tổng này trừ đi tổng các số trong mảng input, kết quả chính là số bị thiếu. Ví dụ: n=4, tổng từ 1-5 là 15. Nếu mảng [1,5,4,3] có tổng 13, số thiếu là 15-13=2.

Lưu ý quan trọng: Phải dùng kiểu dữ liệu long long để tránh tràn số khi n lớn (n=10^5), vì tổng có thể lên tới ~5*10^9.

Cách Phép tính XOR

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;
    long long xor_sum = 0;

    // XOR tất cả các số từ 1 đến n+1
    for (int i = 1; i <= n + 1; i++) {
        xor_sum ^= i;
    }

    // XOR với tất cả các số trong mảng
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        xor_sum ^= x;
    }

    cout << xor_sum;
    return 0;
}

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

Phương pháp này sử dụng phép toán XOR. Đặc tính của XOR: a XOR a = 0 và a XOR 0 = a. Nếu ta XOR tất cả các số từ 1 đến n+1 rồi XOR với tất cả các số trong mảng, các số xuất hiện 2 lần sẽ triệt tiêu nhau (trở thành 0), chỉ còn lại số bị thiếu.

Ví dụ: n=4, XOR [1,2,3,4,5] = X. XOR [1,5,4,3] = Y. Kết quả X XOR Y = 2 (số thiếu).

Ưu điểm: Không lo tràn số như phép tính tổng.

Cách Phép tính tổng tối ưu (1 vòng lặp)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;
    long long s = 0;
    long long maxa = 0;

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        s += x;
        maxa = max(maxa, x);
    }

    cout << (maxa * (maxa + 1) / 2) - s;
}

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

Đây là biến thể của phương pháp tính tổng. Thay vì tính tổng từ 1 đến n+1, ta tính tổng từ 1 đến maxa (số lớn nhất trong mảng). Vì mảng chỉ thiếu đúng 1 số trong khoảng [1, n+1], nên maxa chính là n+1 hoặc n.

Nếu maxa = n+1: Số thiếu nằm trong [1, n]. Nếu maxa = n: Số thiếu chính là n+1.

Phương pháp này cũng cần long long để tránh tràn số.

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

Bài học kinh nghiệm

• Số bị thiếu nằm trong khoảng [1, n+1] và chỉ có duy nhất 1 số này bị thiếu
• Tổng các số từ 1 đến K là K*(K+1)/2 - công thức quan trọng để giải bài toán
• Phép XOR có thể loại bỏ các số xuất hiện 2 lần, để lại số xuất hiện 1 lần (số thiếu)
• Kiểu dữ liệu long long cần thiết để tránh tràn số khi tính tổng với n lớn

Lỗi thường gặp

• Dùng int thay vì long long导致 tràn số khi n=10^5 (tổng ~510^9 > 210^9)
• Quên xử lý trường hợp số thiếu là n+1 (lớn hơn tất cả các số trong mảng)
• Tính sai công thức tổng: phải là (n+1)(n+2)/2 chứ không phải n(n+1)/2
• Không sử dụng fast I/O (cin/cout) có thể gây TLE với n lớn