Làm thế nào để sử dụng kỹ thuật Bit Manipulation nhằm giải quyết bài toán tìm số xuất hiện lẻ lần trong một mảng mà tất cả các số khác đều xuất hiện chẵn lần, và tại sao cách tiếp cận này lại tối ưu về mặt Time Complexity và Space Complexity?

Question

Accepted Answer

Bản chất vấn đề
Khi phát triển phần mềm ở cấp độ Enterprise, việc tối ưu hóa tài nguyên phần cứng (CPU và Memory) luôn được ưu tiên hàng đầu. Bài toán tìm phần tử xuất hiện số lần lẻ trong khi các phần tử khác xuất hiện số lần chẵn là một bài toán kinh điển thường gặp trong việc xử lý log hoặc lọc dữ liệu mạng.
Giải pháp sử dụng Bitwise XOR
Phép toán XOR (ký hiệu là ^) có hai tính chất cốt lõi:

Tính giao hoán và kết hợp: A ^ B ^ A = (A ^ A) ^ B = 0 ^ B = B.
Một số XOR với chính nó sẽ bằng 0: A ^ A = 0.
Một số XOR với 0 sẽ bằng chính nó: A ^ 0 = A.

Khi chúng ta áp dụng phép toán XOR liên tục cho tất cả các phần tử trong mảng, các phần tử xuất hiện chẵn lần sẽ triệt tiêu lẫn nhau (về 0), và phần tử xuất hiện lẻ lần sẽ được giữ lại.
Ví dụ cài đặt mã nguồn bằng JavaScript
function findSingleNumber(nums) {
    let single = 0;
    for (let i = 0; i < nums.length; i++) {
        single ^= nums.nums[i];
    }
    return single;
}

// Ví dụ thực tế
const array = [4, 1, 2, 1, 2];
console.log(findSingleNumber(array)); // Kết quả: 4
Đánh giá chuyên sâu theo tiêu chuẩn Enterprise

Time Complexity: O(N) vì chúng ta chỉ cần duyệt qua mảng đúng một lần duy nhất.
Space Complexity: O(1) vì chỉ sử dụng một biến nhớ phụ trợ (single) để lưu trữ kết quả tạm thời, không phụ thuộc vào kích thước của mảng đầu vào.
Lưu ý thực chiến: Kỹ thuật này tránh được việc phải sử dụng cấu trúc dữ liệu Hash Map, giúp tiết kiệm đáng kể dung lượng RAM và loại bỏ hoàn toàn chi phí phát sinh do Garbage Collection.

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi bit manipulation liên quan cùng chủ đề