Single Number: tại sao XOR thắng hash set

Bạn có một mảng số nguyên trong đó mọi giá trị đều xuất hiện đúng hai lần — ngoại trừ một phần tử cô đơn chỉ xuất hiện một lần. Trả về phần tử đó. Điều kiện ràng buộc: thời gian tuyến tính, không gian hằng số. Bạn không thể sort, không thể dùng set, không thể đếm tần suất trong dictionary. Ràng buộc loại bỏ mọi cấu trúc lưu trữ thông thường trước khi bạn viết một dòng code.

Source solution có hai approach: giải pháp hash set (thỏa mãn về thời gian nhưng không thỏa về không gian) và XOR bit manipulation (đáp ứng cả hai). Cả hai đều đáng tìm hiểu. Hash set cho thấy tại sao cách đặt vấn đề thông thường thất bại. XOR cho thấy một tính chất đại số duy nhất có thể giải quyết toàn bộ bài toán.

Hash set — và tại sao nó không đủ điều kiện

Cách đọc tự nhiên nhất của bài toán này là bài toán tần suất: gặp một số lần đầu thì ghi lại; gặp lần nữa thì đánh dấu là đã ghép cặp. Cuối cùng, ai chưa được ghép cặp chính là đáp án.

Một hash set làm điều đó cụ thể. Nếu số chưa có trong set, thêm vào. Nếu đã có, xóa đi (đó là cặp). Phần còn lại là singleton.

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        seen: set[int] = set()
        for num in nums:
            if num in seen:
                seen.remove(num)
            else:
                seen.add(num)
        return seen.pop()

using System.Collections.Generic;
 
public class Solution {
    public int SingleNumber(int[] nums) {
        var seen = new HashSet<int>();
        foreach (int num in nums) {
            if (seen.Contains(num)) {
                seen.Remove(num);
            } else {
                seen.Add(num);
            }
        }
        foreach (int n in seen) return n;
        return -1; // không thể đến đây theo đảm bảo của bài toán
    }
}

Logic rõ ràng và time complexity ổn: một lần duyệt, mỗi thao tác hash set là O(1) amortized, tổng cộng O(n). Nhưng space là O(n) — trong trường hợp xấu nhất (singleton là phần tử cuối), set giữ (n - 1) / 2 giá trị đồng thời trước khi bất kỳ phần tử nào bị xóa. Với n lên đến 3 * 10^4, đó là khoảng 15,000 số nguyên trong bộ nhớ. Không thảm họa trong thực tế, nhưng không thỏa mãn ràng buộc không gian hằng số của bài toán.

Vậy hash set hữu ích về mặt sư phạm và có thể xuất hiện trong một cuộc phỏng vấn thực tế như một bước trung gian — nó cho thấy bạn hiểu bài toán. Nhưng nó không phải là đáp án.

Trace tay qua hash set

Lấy nums = [7, 3, 5, 3, 7]. Singleton là 5.

Bắt đầu: seen = {}
 
num = 7:  chưa có trong seen -> thêm    seen = {7}
num = 3:  chưa có trong seen -> thêm    seen = {7, 3}
num = 5:  chưa có trong seen -> thêm    seen = {7, 3, 5}
num = 3:  đã có trong seen -> xóa      seen = {7, 5}
num = 7:  đã có trong seen -> xóa      seen = {5}
 
Trả về seen.pop() = 5

Các cặp tự triệt tiêu nhau. Singleton không có partner nên không bao giờ bị xóa. Đây chính xác là điều XOR sẽ làm theo đại số — các cặp triệt tiêu, singleton sống sót — nhưng không có chi phí bộ nhớ.

Những gì ràng buộc thực sự buộc ta phải làm

Với 1 <= nums.length <= 3 * 10^4 và n được đảm bảo là lẻ (một singleton cộng với các cặp), mảng đủ nhỏ để O(n) thời gian là ổn. Ràng buộc quyết định là không gian: cần O(1).

O(1) space có nghĩa là một biến tích lũy duy nhất. Bạn không thể lưu bất kỳ cấu trúc phụ nào tăng theo input. Các phép toán duy nhất bạn có thể thực hiện duy trì trạng thái trong một số nguyên duy nhất là phép toán số học và phép toán bitwise. Câu hỏi đặt ra: có phép toán bitwise nào tự nhiên triệt tiêu các cặp không?

Có, và đó là XOR.

XOR triệt tiêu các cặp — tại sao toán học hoạt động

XOR (^) có ba tính chất quan trọng ở đây:

• a ^ a = 0 (bất kỳ giá trị nào XOR với chính nó là không)
• a ^ 0 = a (không là phần tử trung tính)
• XOR có tính giao hoán và kết hợp — thứ tự không quan trọng

Ba điều này cộng lại có nghĩa là nếu bạn XOR mọi phần tử trong mảng, mọi cặp triệt tiêu về không, và singleton XOR với không chỉ là singleton.

Cụ thể: với [a, b, a, c, b, c, d], tích lũy XOR cho:

a ^ b ^ a ^ c ^ b ^ c ^ d
= (a ^ a) ^ (b ^ b) ^ (c ^ c) ^ d   <- sắp xếp lại hợp lệ, XOR có tính giao hoán
= 0 ^ 0 ^ 0 ^ d
= d

Singleton sống sót. Mọi thứ khác bị triệt tiêu. Đây không phải là một mẹo vặt — đó là hệ quả trực tiếp của ba quy tắc đại số đó.

Cài đặt XOR

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

public class Solution {
    public int SingleNumber(int[] nums) {
        int result = 0;
        foreach (int num in nums) {
            result ^= num;
        }
        return result;
    }
}

Đó là tất cả. Một biến, một lần duyệt, hai tính chất của XOR.

Trace tay qua XOR

Cùng input: nums = [7, 3, 5, 3, 7]. Tôi sẽ theo dõi biểu diễn nhị phân cùng với thập phân để làm cho sự triệt tiêu bit trở nên rõ ràng.

Bắt đầu: result = 0  (0b00000)
 
num = 7:  result = 0 ^ 7  = 7   (0b00000 ^ 0b00111 = 0b00111)
num = 3:  result = 7 ^ 3  = 4   (0b00111 ^ 0b00011 = 0b00100)
num = 5:  result = 4 ^ 5  = 1   (0b00100 ^ 0b00101 = 0b00001)
num = 3:  result = 1 ^ 3  = 2   (0b00001 ^ 0b00011 = 0b00010)
num = 7:  result = 2 ^ 7  = 5   (0b00010 ^ 0b00111 = 0b00101)
 
Trả về 5

Các giá trị trung gian trông hỗn loạn — điều đó được mong đợi. XOR tích lũy từng bit, và trạng thái cuối cùng được xác định bởi những bit nào xuất hiện số lẻ lần trên tất cả các input. Chỉ những bit thuộc về 5 (xuất hiện một lần) sống sót; tất cả các bit khác được đóng góp bởi các giá trị xuất hiện số chẵn lần và bị triệt tiêu.

Các edge case

Mảng một phần tử (nums = [42]): Vòng lặp chạy một lần: result = 0 ^ 42 = 42. Trả về 42. Đúng — không có cặp nào, phần tử duy nhất là singleton hiển nhiên.

Số nguyên âm (nums = [-5, 2, -5]): XOR hoạt động trên biểu diễn two's-complement, và Python/C# đều dùng two's-complement cho số nguyên. (-5) ^ (-5) = 0 đúng vì mọi bit trong -5 được ghép cặp với chính nó. result = 0 ^ 2 = 2. Đúng.

Singleton là phần tử đầu tiên (nums = [9, 4, 4]): Các cặp xuất hiện sau singleton. Vì XOR có tính giao hoán, thứ tự không quan trọng: 9 ^ 4 ^ 4 = 9 ^ (4 ^ 4) = 9 ^ 0 = 9. Đúng.

Singleton là phần tử cuối cùng (nums = [4, 4, 9]): Logic tương tự theo thứ tự khác: 4 ^ 4 ^ 9 = 0 ^ 9 = 9. Đúng.

Tất cả các cặp có giá trị không, singleton khác không (nums = [0, 0, 13]): 0 ^ 0 ^ 13 = 0 ^ 13 = 13. Đúng — không là phần tử trung tính của XOR và không gây ra vấn đề gì.

Complexity

Cả hai đều là single-pass linear time. Sự khác biệt hoàn toàn là về không gian. Approach XOR sử dụng cùng một lượng bộ nhớ bất kể kích thước input — chỉ một thanh ghi số nguyên.

Cái nào để ship, và tại sao

XOR là đáp án duy nhất đúng theo ràng buộc. Tôi sẽ viết nó ngay trong một buổi phỏng vấn, nhưng tôi sẽ giải thích trực giác hash set trước để chứng minh rằng tôi hiểu bài toán trước khi dùng bit trick. Hash set làm cho mô hình "triệt tiêu cặp" rõ ràng theo cách XOR không làm — và việc cho thấy bạn có thể suy ra tính chất XOR từ trực giác set ("nếu chúng ta có thể triệt tiêu các cặp mà không lưu chúng thì sao?") mạnh hơn là kéo trick từ bộ nhớ.

Trong code production, phiên bản XOR cũng tốt hơn tuyệt đối: ngắn hơn, cache-friendly (không cấp phát hash table), và đúng trên các edge case mà không cần xử lý đặc biệt. Không có lý do gì để ưu tiên hash set ở đây.

Pattern cơ bản: bit-parity accumulation

Mental model có thể chuyển giao là: XOR tích lũy parity của từng vị trí bit trên tất cả các input. Một bit được set số chẵn lần là không trong kết quả. Một bit được set số lẻ lần là một trong kết quả. Khi mọi giá trị xuất hiện đúng hai lần ngoại trừ một, bit pattern của kết quả chính xác là bit pattern của singleton — vì chỉ những bit của nó đóng góp với parity lẻ.

Pattern "parity accumulation" này xuất hiện trong nhiều bài toán bit manipulation. Khi bạn thấy XOR như một bộ phát hiện parity hơn là chỉ một cổng logic, một gia đình bài toán mở ra.

Vị trí trong series và những gì tiếp theo

Đây là điểm vào của series bit manipulation — bài toán giới thiệu XOR như một công cụ cho điều gì đó không hiển nhiên. Nếu bạn thoải mái với bài này, các bài anh em leo thang ràng buộc:

Single Number II (137) đẩy giả định ghép cặp: bây giờ mọi phần tử xuất hiện đúng ba lần ngoại trừ một. a ^ a ^ a != 0 nên XOR một mình không triệt tiêu được. Bạn cần theo dõi số lượng bit modulo 3, đòi hỏi duy trì hai accumulator (ones và twos) để biểu diễn bộ đếm 3 trạng thái cho mỗi bit. Tư duy XOR tương tự được áp dụng, nhưng thiết kế accumulator phức tạp hơn.

Single Number III (260) tiến xa hơn: hai phần tử mỗi cái xuất hiện một lần, mọi thứ khác hai lần. Một lần XOR pass cho bạn XOR của hai singleton, không phải một trong hai. Bạn sau đó cần cô lập một bit khác nhau giữa chúng (bit thấp nhất được set trong XOR của chúng), chia mảng theo bit đó, và XOR từng partition riêng biệt. Hai lần duyệt, hai accumulator — và insight chính vẫn là XOR parity.

Find the Difference (389) là cùng một core trick được áp dụng cho string: cho một string s và một phiên bản xáo trộn t với một ký tự thêm, tìm ký tự thêm đó. XOR tất cả ký tự của cả hai string với nhau; các cặp triệt tiêu và ký tự thêm sống sót. Code gần như giống hệt bài toán này.

Missing Number (268) là người họ hàng: cho [0, n] với một số bị thiếu, XOR mảng với [0, 1, ..., n]. Các số hiện diện triệt tiêu nhau theo cặp (giá trị mảng XOR giá trị range), và chỉ giá trị range của số bị thiếu còn lại không có cặp. Trick đòi hỏi biết range dự kiến, điều mà bài toán này không có — nhưng cấu trúc đại số là như nhau.