2. Phân tích và ý tưởng

Nếu biết tổng của tất cả các số từ ~1~ đến ~n~, sau đó trừ đi tổng của ~n - 1~ số đã cho, phần còn lại chính là số bị thiếu.

Tổng các số nguyên liên tiếp từ ~1~ đến ~n~ được tính bằng công thức:

~S = n × (n + 1) / 2~

Gọi ~T~ là tổng các số xuất hiện trong dữ liệu vào. Khi đó:

~K = S - T~

Trong đó ~K~ là số cần tìm.

Vì sao đúng? Mỗi số từ ~1~ đến ~n~ xuất hiện đúng một lần trong tổng ~S~. Khi trừ đi toàn bộ các số được cung cấp, tất cả các số đã xuất hiện đều bị triệt tiêu, chỉ còn lại số bị thiếu.

3. Các bước thực hiện

1. Nhập ~n~.
2. Tính ~S = n × (n + 1) / 2~.
3. Lần lượt đọc ~n - 1~ số, trừ từng số khỏi ~S~.
4. In ~S~; đây chính là số bị thiếu.

Mô phỏng ví dụ: Với ~n = 5~, ta có ~S = 5 × 6 / 2 = 15~. Đọc lần lượt ~2, 1, 5, 4~ và trừ khỏi ~S~:

Kết quả: ~3~.

4. Chương trình C++ tham khảo

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

long long n, x, s;

int main() {
    cin >> n;
    s = n * (n + 1) / 2;

    for (int i = 1; i < n; i++) {
        cin >> x;
        s -= x;
    }

    cout << s << endl;
    return 0;
}

5. Đánh giá độ phức tạp

• Thời gian: ~O(n)~, vì cần đọc ~n - 1~ số và thực hiện một phép trừ cho mỗi số.
• Bộ nhớ phụ: ~O(1)~, vì chỉ sử dụng một số biến, không cần lưu cả dãy vào mảng.

6. Lưu ý quan trọng

• Với ~n = 200000~, tổng ~1 + 2 + ... + n = 20000100000~, vượt giới hạn của kiểu int 32 bit. Vì vậy cần dùng long long cho biến n và s.
• Không cần sắp xếp hoặc lưu dãy vào mảng.
• Trường hợp ~n = 1~, không có số nào được nhập thêm và kết quả là ~1~.
• Không nhầm số lượng phần tử được nhập là ~n~: chỉ có ~n - 1~ số.