Tìm thẻ bị mất

Nguồn: Bài tập Facebook (giống CSES 1083 Missing Number) Độ khó: Dễ Toán học Cấp số cộng Mảng đánh dấu

Đề bài

Đề bài tìm thẻ bị mất: Có một bộ thẻ bài gồm $N$ quân bài được đánh số từ $1$ đến $N$, trong đó có một tấm thẻ đã bị mất. Hãy xác định xem quân bài nào bị mất.

Đầu vào:

• Dòng đầu tiên chứa số $N$.
• $N - 1$ số sau là số của các tấm thẻ còn lại.

Ràng buộc: $2 \le N \le 1\,000\,000$.

Đầu ra: Số duy nhất là số của tấm thẻ bị mất.

Ví dụ – input

10
4 1 7 8 3 5 9 10 6

Ví dụ – output

2

Lời mở đầu

Nay mình đi comment dạo thấy bài này cũng được (một bạn đăng hỏi vì thấy "khó hiểu quá"), nên đăng để anh em thử sức, và viết luôn bài giải chi tiết để nhiều bạn được tham khảo. Hy vọng mang đến được giá trị cho các bạn 😇.

Bài này giống hệt bài Missing Number trên CSES, chỉ khác là bên đó $2 \le n \le 2 \cdot 10^5$. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link dưới đây nha:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ mẫu: $N = 10$ nên bộ bài đầy đủ gồm các lá $1, 2, 3, \ldots, 10$. Các lá còn lại là $4, 1, 7, 8, 3, 5, 9, 10, 6$ (đúng $N - 1 = 9$ lá, không theo thứ tự). Dò lại thì thấy thiếu lá số $2$ ⇒ đáp án là $2$.

Bên dưới bài đăng có khá nhiều bạn comment các cách cao siêu quá 😅, trong khi vấn đề hết sức đơn giản để nhìn ra. Mình trình bày 2 cách: cách đánh dấu bằng mảng mà nhiều bạn hay nghĩ tới trước, và cách dùng công thức tổng mà mình hướng dẫn.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Mảng đánh dấu · O(N) bộ nhớCách 2Tổng cấp số cộng · O(1) bộ nhớ

Cách 1Đánh dấu các lá bài đã thấy – O(N)

Ta dùng một mảng mark với mark[x] = true nghĩa là lá bài số $x$ đang còn. Đọc $N - 1$ lá bài, gặp lá nào thì đánh dấu lá đó. Sau cùng duyệt $i$ từ $1$ đến $N$, lá nào chưa được đánh dấu chính là lá bị mất.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
using namespace std;

bool mark[1000001]; // mark[x] = true nếu đã thấy lá bài số x

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i = 1; i <= n - 1; i++)
    {
        int x;
        cin >> x;
        mark[x] = true;
    }
    for(int i = 1; i <= n; i++)
    {
        if(mark[i] == false)
        {
            cout << i;
            break;
        }
    }
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
mark = [False] * (n + 1)  # mark[x] = True nếu đã thấy lá bài số x
for i in range(1, n):
    mark[int(data[i])] = True
for i in range(1, n + 1):
    if not mark[i]:
        print(i)
        break

C++▶ Chạy tay từng dòng codeĐánh dấu các lá còn lại, lá nào chưa đánh dấu là lá bị mất.

Dữ liệu vào (stdin) – sửa thoải mái10 4 1 7 8 3 5 9 10 6

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4bool mark[1000001]; // mark[x] = true nếu đã thấy lá bài số x

5

6int main()

7{

8 ios_base::sync_with_stdio(false);

9 cin.tie(NULL);

10 int n;

11 cin >> n;

12 for(int i = 1; i <= n - 1; i++)

13 {

14 int x;

15 cin >> x;

16 mark[x] = true;

17 }

18 for(int i = 1; i <= n; i++)

19 {

20 if(mark[i] == false)

21 {

22 cout << i;

23 break;

24 }

25 }

26 return 0;

27}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: cần mảng đánh dấu $N + 1$ phần tử: $O(N)$.
• Thời gian: đọc $N - 1$ số rồi duyệt lại $N$ phần tử: $O(N)$.

Không gian$O(N)$

Thời gian$O(N)$

Coi chừng khai báo mảng thiếu

Lá bài lớn nhất có thể là $N = 10^6$ (lá bị mất cũng có thể chính là $999999$ hay $10^6$), nên mảng đánh dấu phải có đủ chỉ số tới $10^6$, và nên khai báo toàn cục để không bị tràn stack. Bạn nào khai báo mảng nhỏ hơn là bị lỗi ngay ở các test lớn.

Cách 2Tổng 1 + 2 + ... + N trừ tổng các lá còn lại – O(N), không cần mảng

Vấn đề hết sức đơn giản để nhìn ra mà: nếu giả sử lá bài đó không bị mất thì ta có đủ $N$ lá bài từ $1$ đến $N$. Còn giờ bị thiếu lá bài đó, thì đơn giản:

• Tính tổng các lá bài từ $1$ đến $N$ bằng công thức cấp số cộng: $\dfrac{N \cdot (N + 1)}{2}$.
• Sau đó trừ cho tổng các lá bài đang có là sẽ ra được lá bài bị thiếu.

Công thức

$\text{lá bị mất} = \dfrac{N \cdot (N + 1)}{2} - (a_1 + a_2 + \ldots + a_{N-1})$

Như trong ví dụ mẫu, tổng từ $1$ đến $10$ là $\dfrac{10 \cdot 11}{2} = 55$. Tổng mảng input đang có là $4 + 1 + 7 + 8 + 3 + 5 + 9 + 10 + 6 = 53$. Vậy lúc này lấy $55 - 53 = 2$ chính là đáp án lá bài thiếu cần tìm. Đơn giản vậy thôi! Chẳng cần mảng luôn, chỉ cần duyệt vòng lặp cộng dồn nhé 😃.

Các bạn nhập thử bộ bài rồi bấm Tiếp để xem từng lá được cộng vào tổng:

N Các lá còn lại

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n;
    cin >> n;
    long long sum = 0;
    long long temp = n - 1;
    while(temp--)
    {
        long long x;
        cin >> x;
        sum += x;
    }
    cout << (n * (n + 1)) / 2 - sum;
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
s = 0
for i in range(1, n):
    s += int(data[i])
print(n * (n + 1) // 2 - s)

Mình chỉnh nhẹ số lần lặp

Đoạn code mình gõ nhanh trong comment ban đầu dùng temp = n nên vòng while(temp--) đọc tới $N$ số, trong khi đầu vào chỉ có $N - 1$ số. Lần đọc cuối bị thất bại thì C++ (từ C++11) gán x = 0 nên kết quả vẫn đúng, nhưng như vậy là "đúng nhờ may mắn". Ở đây mình sửa thành temp = n - 1 cho chuẩn. Mình cũng thêm 2 dòng ios_base::sync_with_stdio(false); cin.tie(NULL); để đọc $10^6$ số cho nhanh.

C++▶ Chạy tay từng dòng codesum = tổng N − 1 lá còn lại; đáp án = N·(N + 1)/2 − sum.

Dữ liệu vào (stdin) – sửa thoải mái10 4 1 7 8 3 5 9 10 6

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main()

5{

6 ios_base::sync_with_stdio(false);

7 cin.tie(NULL);

8 long long n;

9 cin >> n;

10 long long sum = 0;

11 long long temp = n - 1;

12 while(temp--)

13 {

14 long long x;

15 cin >> x;

16 sum += x;

17 }

18 cout << (n * (n + 1)) / 2 - sum;

19 return 0;

20}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ dùng vài biến, không cần mảng: $O(1)$.
• Thời gian: đọc và cộng $N - 1$ số: $O(N)$.

Không gian$O(1)$

Thời gian$O(N)$

Nhớ dùng long long

Với $N = 10^6$ thì $\dfrac{N \cdot (N + 1)}{2} \approx 5 \cdot 10^{11}$, vượt xa giới hạn kiểu int (khoảng $2.1 \cdot 10^9$). Vì vậy n, sum đều phải khai báo long long, nếu không phép nhân n * (n + 1) sẽ bị tràn số.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 500 bộ test ngẫu nhiên ($N \le 30$, lá bị mất ở vị trí bất kỳ), so với đáp án đúng – khớp hết. Với $N = 10^6$ (mất lá $999999$): cách 2 bản C++ chạy khoảng 0.15 giây, bản Python khoảng 0.9 giây; cách 1 bản C++ dưới 0.5 giây, bản Python khoảng 1.5 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇