Mô phỏng thuật toán Số xuất hiện một lần (XOR)

Single Number (XOR) · Nhóm: Bit & Mặt nạ

Trong mảng mà mọi số xuất hiện đúng hai lần trừ một số duy nhất, XOR tất cả lại thì các cặp trùng triệt tiêu, chỉ còn số lẻ.

Ý tưởng

Khởi tạo acc = 0 (phần tử trung hoà của XOR: x ^ 0 = x).

Duyệt một lượt, dồn acc = acc ^ a[i] cho mọi phần tử.

Nhờ x ^ x = 0, mỗi cặp bằng nhau cho 0; kết quả cuối là số xuất hiện một lần.

Vì sao đúng

XOR có tính giao hoán và kết hợp nên có thể gom các số bằng nhau lại; cặp nào cũng tự huỷ, số cô đơn sống sót mà không cần bộ nhớ phụ.

Mã Python

def single_number(a):
    acc = 0                 # XOR identity: x ^ 0 = x
    for x in a:            # walk every element once
        acc ^= x          # equal pairs cancel: x ^ x = 0
    return acc            # the lone element survives

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.