Bài Toán Single Number II: Tìm Số Xuất Hiện 1 Lần Trong Mảng Các Số Khác Xuất Hiện 3 Lần

Đề bài: Cho mảng số nguyên không rỗng, mọi phần tử xuất hiện 3 lần trừ 1 phần tử xuất hiện 1 lần. Tìm phần tử đó.

Ví dụ: [2,2,3,2] → kết quả 3.

Ý tưởng giải (Bit Manipulation)

Đếm số lần bit 1 xuất hiện ở mỗi vị trí (0–31) trên tất cả số. Vì các số khác xuất hiện 3 lần, tổng bit tại mỗi vị trí sẽ chia hết cho 3, trừ bit của số độc nhất. Lấy phần dư mod 3 để khôi phục số kết quả.

Code Python (Tối ưu O(n) time, O(1) space)

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        # 32 bit cho signed integer
        bit_counts = [0] * 32
        
        for num in nums:
            for i in range(32):
                # Lấy bit thứ i (từ LSB)
                if num & (1 << i):
                    bit_counts[i] += 1
        
        # Khôi phục kết quả từ bit_counts % 3
        result = 0
        for i in range(32):
            if bit_counts[i] % 3:
                result |= (1 << i)
        
        # Xử lý số âm (2's complement): nếu bit 31 (sign bit) = 1
        if result >= 2**31:
            result -= 2**32
        
        return result

# Test
ob = Solution()
print(ob.singleNumber([2, 2, 3, 2]))        # 3
print(ob.singleNumber([0, 1, 0, 1, 0, 1, 99]))  # 99
print(ob.singleNumber([-2, -2, -2, -3]))    # -3

Giải thích xử lý số âm

Python dùng integer tùy ý độ chính xác (arbitrary precision), không cố định 32 bit. Khi khôi phục, nếu bit 31 = 1, ta coi đó là số âm trong 2's complement 32-bit: trừ 2**32 để ra giá trị âm đúng.

Phương pháp thay thế: Counter (đơn giản hơn, O(n) space)

from collections import Counter

def singleNumber(nums):
    count = Counter(nums)
    for num, freq in count.items():
        if freq == 1:
            return num

Kết luận

Bit manipulation là giải pháp tối ưu space O(1), thường được hỏi trong phỏng vấn. Counter dễ đọc hơn cho production code.