Cấu trúc dữ liệu và Giải thuật Bài 27: Tìm kiếm phần tử bị thiếu/lặp lại bằng XOR và Toán học.

Giả sử bạn đang rà soát hàng triệu bản ghi ID người dùng được sinh ra tuần tự từ 1 đến $N$. Do một lỗi trong quá trình đồng bộ (race condition) trên hệ thống phân tán, một ID đã bị biến mất. Làm thế nào để tìm ra con số thất lạc đó trong thời gian $O(n)$ mà không sử dụng thêm bất kỳ một Byte RAM nào ($O(1)$ không gian)?

Nếu dùng Hash Map, bạn sẽ tốn $O(n)$ RAM. Nếu dùng thuật toán sắp xếp (Sorting), bạn sẽ mất $O(n \log n)$ thời gian CPU. Đây là lúc chúng ta phải triệu hồi sức mạnh của Toán học và các phép toán thao tác Bit (Bitwise).

1. Phương pháp Toán học: Tổng cấp số cộng

Dựa trên công thức kinh điển của nhà toán học Carl Friedrich Gauss, tổng của một dãy số liên tiếp từ 1 đến $N$ được tính bằng công thức:

$$S = \frac{n \times (n + 1)}{2}$$

Cơ chế tìm kiếm:

1. Tính tổng kỳ vọng (Expected Sum) của mảng hoàn hảo từ 1 đến $N$ bằng công thức trên.

2. Dùng một vòng lặp duyệt qua mảng hiện tại để tính tổng thực tế (Actual Sum).

3. Lấy Tổng kỳ vọng trừ đi Tổng thực tế, phần dư ra chính là con số bị thiếu.

Go

func missingNumberMath(nums []int) int {
    n := len(nums)
    expectedSum := n * (n + 1) / 2
    
    actualSum := 0
    for _, num := range nums {
        actualSum += num
    }
    
    return expectedSum - actualSum
}

Cạm bẫy chí mạng (Integer Overflow):

Phương pháp toán học rất thanh lịch, nhưng nó chứa một "quả bom nổ chậm". Khi lập trình C/C++ trên các vi điều khiển như STM32 hay ESP32, kích thước thanh ghi (Register) cực kỳ giới hạn. Nếu $N = 1,000,000$, tổng kỳ vọng sẽ là khoảng $500 \times 10^9$. Con số này vượt quá giới hạn lưu trữ của kiểu dữ liệu int32 (tối đa khoảng $2.14 \times 10^9$). Phép tính sẽ bị tràn số (Overflow), biến kết quả thành một số âm vô nghĩa và phá hỏng toàn bộ logic của phần mềm.

2. Phép màu của XOR (Exclusive OR)

Để vượt qua bài toán tràn số, chúng ta đi sâu vào tầng vật lý của CPU với phép toán XOR (ký hiệu là ^ trong code, hoặc $\oplus$ trong toán học).

Phép XOR so sánh từng bit của 2 số nguyên. Quy tắc cốt lõi: Giống nhau thì bằng 0, Khác nhau thì bằng 1.

Từ quy tắc này, XOR sinh ra 3 tính chất thần thánh:

1. Tự triệt tiêu: $A \oplus A = 0$ (Hai số giống hệt nhau XOR với nhau sẽ biến mất).

2. Định danh: $A \oplus 0 = A$ (Một số XOR với 0 vẫn là chính nó).

3. Giao hoán và Kết hợp: $A \oplus B \oplus C = A \oplus C \oplus B$ (Thứ tự thực hiện không quan trọng).

Logic tìm số bị thiếu bằng XOR:

Nếu chúng ta lấy tất cả các số từ 1 đến $N$, đem XOR với toàn bộ các phần tử đang có trong mảng. Các con số giống nhau sẽ tự động bắt cặp với nhau và triệt tiêu thành 0. Con số duy nhất không bị triệt tiêu chính là con số bị thiếu.

Go

func missingNumberXOR(nums []int) int {
    missing := len(nums) // Khởi tạo bằng giá trị N
    
    for i, num := range nums {
        // XOR chỉ mục i (đại diện cho mảng chuẩn) và num (giá trị thực tế)
        missing = missing ^ i ^ num
    }
    
    return missing
}

Mô phỏng với mảng [0, 1, 3] (N = 3, thiếu số 2):

• Khởi tạo missing = 3

• Vòng 0 (i=0, num=0): missing = 3 ^ 0 ^ 0 = 3

• Vòng 1 (i=1, num=1): missing = 3 ^ 1 ^ 1 = 3

• Vòng 2 (i=2, num=3): missing = 3 ^ 2 ^ 3

• Sắp xếp lại theo tính chất giao hoán: (3 ^ 3) ^ 2 = 0 ^ 2 = 2.

• Kết quả cuối cùng là 2. Tốc độ thực thi chớp nhoáng ở cấp độ vi mạch, và vĩnh viễn không bao giờ bị tràn số.

3. Mở rộng: Bài toán 2 lỗi (Thiếu 1 số, Lặp 1 số)

Giả sử dữ liệu không chỉ bị mất 1 số, mà còn có 1 số bị ghi đè lên làm nó xuất hiện 2 lần (Ví dụ: [1, 2, 2, 4]). Hãy tìm cả số bị thiếu và số bị lặp.

Lúc này, nếu gọi $X$ là số bị lặp và $Y$ là số bị thiếu. Khi gom tất cả lại và XOR, kết quả cuối cùng sẽ là $X \oplus Y$. Vì $X \neq Y$, kết quả này chắc chắn khác 0 (nghĩa là có ít nhất 1 bit mang giá trị 1).

Chúng ta sử dụng chính bit khác biệt này như một "vách ngăn" để chia toàn bộ mảng thành 2 nhóm:

• Nhóm 1: Các số có bit đó bằng 1 (chắc chắn chứa $X$).

• Nhóm 2: Các số có bit đó bằng 0 (chắc chắn chứa $Y$).

Bằng cách XOR riêng rẽ từng nhóm một lần nữa, hai con số $X$ và $Y$ sẽ tự động "rụng" ra. Kỹ thuật chia để trị bằng Bit này giúp duy trì độ phức tạp thời gian ở mức $O(n)$ mà không cần cấu trúc dữ liệu phụ trợ.

4. Ứng dụng ở tầng Hệ thống

Kỹ thuật Bitwise không phải là trò ảo thuật phòng phỏng vấn, nó là lõi của các hệ thống an toàn dữ liệu:

• RAID 4/5 (Redundant Array of Independent Disks): Các hệ thống máy chủ lưu trữ chia nhỏ file vào nhiều ổ cứng vật lý và dùng một ổ cứng riêng chứa "Bit chẵn lẻ" (Parity Bit) tính bằng phép XOR. Khi một ổ cứng bị hỏng (mất dữ liệu), vi điều khiển của RAID chỉ cần lấy dữ liệu của các ổ cứng còn lại XOR với nhau để khôi phục chính xác 100% dữ liệu đã mất.

• Checksum trong IoT: Khi truyền dữ liệu qua chuẩn giao tiếp UART hoặc SPI giữa các vi điều khiển, đường truyền thường bị nhiễu. Bằng cách nối thêm một byte XOR (Checksum byte) vào cuối gói tin, vi điều khiển nhận có thể phát hiện ngay lập tức nếu gói tin bị sai lệch trong quá trình di chuyển.

Chúng ta đã khai thác mảng tĩnh, mảng động, và mảng đa chiều dưới nhiều góc độ toán học và thuật toán. Tuy nhiên, mọi thứ đều dựa trên một khối bộ nhớ liên tục. Khi RAM của hệ thống bị phân mảnh nặng nề, việc cấp phát một mảng lớn trở nên bất khả thi. Ở bài học tiếp theo, chúng ta sẽ đập tan giới hạn vật lý này bằng một cấu trúc dữ liệu mới: Danh sách liên kết.