Single NumberとXORの性質

Single Number 問題

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n
    return result

# All pairs cancel, leaving the lone element
print(single_number([2, 2, 1]))              # 1
print(single_number([4, 1, 2, 1, 2]))        # 4
print(single_number([1]))                    # 1
print(single_number([7, 3, 5, 3, 7]))        # 5

# Even more concise with functools.reduce
from functools import reduce
from operator import xor
print(reduce(xor, [2, 2, 1]))  # 1

XOR が機能する理由：3つの重要な性質

# Demonstrating the three XOR properties
print('Self-inverse: a ^ a = 0')
for a in [5, 13, 255, 0]:
    print(f'  {a} ^ {a} = {a ^ a}')

print('Identity: a ^ 0 = a')
for a in [5, 13, 0, 1024]:
    print(f'  {a} ^ 0 = {a ^ 0}')

print('Commutativity and Associativity:')
a, b, c = 3, 5, 7
print(f'  a^b^c = {a^b^c}')
print(f'  c^a^b = {c^a^b}')  # same result
print(f'  (a^b)^c = {(a^b)^c}')
print(f'  a^(b^c) = {a^(b^c)}')  # same result

Single Number を順に追跡する

nums = [4, 1, 2, 1, 2]
result = 0
print(f'Start: result = {result} ({bin(result)})')
for n in nums:
    prev = result
    result ^= n
    print(f'XOR {n:2d}: {bin(prev):8s} ^ {bin(n):6s} = {bin(result):8s} = {result}')
print(f'Final: {result}')  # 4

# Alternative: show pair cancellation
print('\nMath view:')
print('4 ^ 1 ^ 2 ^ 1 ^ 2')
print('= 4 ^ (1^1) ^ (2^2)')
print('= 4 ^  0   ^  0')
print('= 4')

Single Number II：すべての要素が3回現れる場合

def single_number_II(nums):
    ones, twos = 0, 0
    for n in nums:
        ones = (ones ^ n) & ~twos   # bits seen 1 mod 3 times
        twos = (twos ^ n) & ~ones   # bits seen 2 mod 3 times
    return ones  # bits seen exactly once

print(single_number_II([2, 2, 3, 2]))    # 3
print(single_number_II([0, 1, 0, 1, 0, 1, 99]))  # 99

# Simpler but O(32) bit-by-bit approach
def single_number_II_simple(nums):
    result = 0
    for bit in range(32):
        total = sum((n >> bit) & 1 for n in nums)
        if total % 3 == 1:
            result |= (1 << bit)
    return result

print(single_number_II_simple([2, 2, 3, 2]))  # 3

Single Number III：2つの要素が1回ずつ現れる場合

def single_number_III(nums):
    xor_all = 0
    for n in nums:
        xor_all ^= n              # xor_all = a ^ b

    diff = xor_all & (-xor_all)  # isolate lowest differing bit

    a = 0
    for n in nums:
        if n & diff:              # group 1: has the diff bit set
            a ^= n
    b = xor_all ^ a              # a ^ b ^ a = b
    return [a, b]

print(sorted(single_number_III([1, 2, 1, 3, 2, 5])))   # [3, 5]
print(sorted(single_number_III([-1, 0])))               # [-1, 0]
print(sorted(single_number_III([0, 1])))                # [0, 1]

XOR で欠落した数を見つける

def missing_number_xor(nums):
    n = len(nums)
    result = n              # start with n (the last expected value)
    for i, num in enumerate(nums):
        result ^= i ^ num   # XOR with both index and value
    return result

def missing_number_sum(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

for nums, expected in [([3,0,1], 2), ([0,1], 2), ([9,6,4,2,3,5,7,0,1], 8)]:
    xor_ans = missing_number_xor(nums)
    sum_ans = missing_number_sum(nums)
    print(f'nums={nums}: XOR={xor_ans}, Sum={sum_ans}, expected={expected}')

一時変数なしで XOR によって入れ替える

# XOR swap
a, b = 17, 42
print(f'Before: a={a}, b={b}')
a ^= b   # a = 17 ^ 42
b ^= a   # b = 42 ^ (17 ^ 42) = 17
a ^= b   # a = (17 ^ 42) ^ 17 = 42
print(f'After:  a={a}, b={b}')   # a=42, b=17

# The caveat: same variable/reference => broken
c = 99
# If a and b pointed to same value:
c ^= c   # c = 0  (destroyed!)
print(f'Same-variable XOR swap: c={c}')  # 0, not 99

# Pythonic swap: always prefer this
a, b = 17, 42
a, b = b, a   # safe, clear, handles aliases
print(f'Pythonic: a={a}, b={b}')

XOR とハッシュおよびチェックサム

# Simple XOR checksum
def xor_checksum(data):
    result = 0
    for byte in data:
        result ^= byte
    return result

data = [0x48, 0x65, 0x6C, 0x6C, 0x6F]  # 'Hello' in ASCII
checksum = xor_checksum(data)
print(f'Checksum: {hex(checksum)}')

# Detect corruption
corrupted = data[:]
corrupted[2] ^= 0xFF   # flip all bits of 3rd byte
new_checksum = xor_checksum(corrupted)
print(f'Original checksum: {hex(checksum)}')
print(f'Corrupted checksum: {hex(new_checksum)}')
print(f'Error detected: {checksum != new_checksum}')

# RAID-5 parity recovery
d1 = [1, 0, 1, 1]
d2 = [0, 1, 1, 0]
parity = [d1[i] ^ d2[i] for i in range(4)]
recovered = [parity[i] ^ d2[i] for i in range(4)]  # recover d1
print(f'd1={d1}, parity={parity}, recovered={recovered}')

XOR と部分集合の問題

from itertools import combinations
from functools import reduce
from operator import xor

def xor_of_all_subsets(arr):
    n = len(arr)
    total_xor = 0
    for r in range(1, n + 1):
        for subset in combinations(arr, r):
            subset_xor = reduce(xor, subset)
            total_xor ^= subset_xor
    return total_xor

# For n > 1, each element appears 2^(n-1) times (even) => cancels
# Result is always 0 for n > 1
for arr in [[1,2,3], [5,7], [1], [1,2,3,4]]:
    result = xor_of_all_subsets(arr)
    predicted = arr[0] if len(arr) == 1 else 0
    print(f'arr={arr}: XOR of all subsets = {result}, predicted = {predicted}')

面接で使えるパターン：一意性のための XOR

def single_number_k_times(nums, k):
    '''Find the element that appears m times when all others appear k times.'''
    # Count each bit's occurrence and take mod k
    result = 0
    for bit in range(32):
        total = sum((n >> bit) & 1 for n in nums)
        if total % k != 0:
            result |= (1 << bit)
    # Handle negative 32-bit numbers
    if result >= (1 << 31):
        result -= (1 << 32)
    return result

# k=2, element appears once
print(single_number_k_times([2,2,1], 2))         # 1
# k=3, element appears once
print(single_number_k_times([2,2,3,2], 3))       # 3
# k=4, element appears once
print(single_number_k_times([1,1,1,1,7,2,2,2,2], 4))  # 7

XOR に関するよく出る面接問題

# Find the difference between two strings
def find_the_difference(s, t):
    result = 0
    for c in s + t:
        result ^= ord(c)
    return chr(result)

print(find_the_difference('abcd', 'abcde'))  # 'e'

# Hamming distance: count differing bits
def hamming_distance(x, y):
    diff = x ^ y
    count = 0
    while diff:
        count += diff & 1
        diff >>= 1
    return count
    # or: bin(x ^ y).count('1')

print(hamming_distance(1, 4))   # 2: 001 vs 100 differ in bits 0 and 2
print(hamming_distance(3, 1))   # 1: 011 vs 001 differ in bit 1

# Prefix XOR for range queries
def xor_queries(arr, queries):
    prefix = [0] * (len(arr) + 1)
    for i, v in enumerate(arr):
        prefix[i+1] = prefix[i] ^ v
    return [prefix[r+1] ^ prefix[l] for l, r in queries]

print(xor_queries([1,3,4,8], [[0,1],[1,2],[0,3],[3,3]]))

理解度チェック

レッスンのまとめ