Single Number dan Sifat XOR
Gunakan sifat invers-sendiri XOR untuk menemukan satu elemen yang muncul sekali dalam daftar, sementara semua elemen lain muncul dua kali, lalu kembangkan ke single-number-II dan III
Single Number dan Sifat XOR adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Masalah Angka Tunggal
Masalah Angka Tunggal (LeetCode 136) menanyakan: jika diberikan sebuah larik yang setiap elemennya muncul tepat dua kali kecuali satu elemen, temukan elemen yang hanya muncul satu kali. Batasan waktu O(n) dan ruang O(1) menyingkirkan peta hash (ruang O(n)) dan pengurutan (waktu O(n log n) atau ruang O(n) yang digunakan oleh pengurutan).
Solusi elegan menggunakan XOR. Lakukan operasi XOR terhadap semua elemen. Karena elemen identik saling membatalkan (a ^ a = 0) dan XOR bersifat komutatif serta asosiatif, semua elemen berpasangan lenyap, menyisakan hanya elemen tunggal. Ini adalah salah satu solusi O(n)/O(1) yang paling memuaskan dalam seluruh pemrograman kompetitif.
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])) # 1Mengapa XOR Berfungsi: Tiga Sifat Utama
Kekuatan XOR berasal dari tiga sifat aljabar yang bekerja bersama:
- Invers terhadap dirinya sendiri:
a ^ a = 0— nilai identik saling meniadakan - Identitas:
a ^ 0 = a— XOR dengan nol tidak mengubah nilai - Komutativitas dan Asosiativitas: urutan tidak berpengaruh dan pengelompokan tidak berpengaruh
Ketiga sifat ini bersama-sama berarti bahwa operasi XOR pada sebuah multihimpunan menyederhanakan semua elemen yang muncul sebanyak genap kali menjadi 0, dan hanya menyisakan elemen yang muncul sebanyak ganjil kali. Dalam Angka Tunggal I, tepat satu elemen muncul satu kali (ganjil), sehingga elemen tersebut adalah hasil XOR.
# 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 resultMenelusuri Angka Tunggal
Marilah kita menelusuri [4, 1, 2, 1, 2] langkah demi langkah untuk melihat pembatalan secara langsung. Kita melakukan XOR terhadap semua elemen: 4 ^ 1 ^ 2 ^ 1 ^ 2. Karena XOR bersifat komutatif, kita dapat mengubah urutannya menjadi (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4. Pasangan-pasangan tersebut saling membatalkan dan hanya menyisakan 4.
Dalam algoritme sebenarnya, kita tidak mengubah urutan—kita melakukan XOR dari kiri ke kanan. Namun, hasil akhirnya tetap sama karena komutativitas dan asosiativitas menjamin bahwa urutan tidak memengaruhi hasil. Anda dapat membayangkan pasangan-pasangan tersebut dikelompokkan di mana saja, dan semuanya akan saling membatalkan.
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')Angka Tunggal II: Setiap Elemen Muncul Tiga Kali
Angka Tunggal II (LeetCode 137): setiap elemen muncul tiga kali kecuali satu elemen yang muncul satu kali. XOR saja tidak berfungsi—pasangan tidak lagi saling membatalkan dalam kelompok tiga. Sebagai gantinya, hitung berapa kali setiap bit muncul di seluruh bilangan. Jika sebuah bit terdapat dalam elemen target, kontribusinya 1; dalam elemen yang muncul tiga kali, kontribusinya 3. Ambil jumlah modulo 3 untuk setiap bit guna mengisolasi bit-bit elemen target.
Kita dapat menyimulasikannya dengan dua variabel bilangan bulat ones dan twos yang bertindak sebagai pencacah tingkat bit modulo 3. Ini adalah pendekatan logika digital: ones menyimpan bit yang terlihat sebanyak ganjil kali modulo 2, sedangkan twos menyimpan bit yang terlihat dua kali modulo 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])) # 3Angka Tunggal III: Dua Elemen Muncul Satu Kali
Angka Tunggal III (LeetCode 260): dua elemen masing-masing muncul satu kali; semua elemen lainnya muncul dua kali. Lakukan XOR terhadap semua elemen untuk mendapatkan a ^ b (XOR dari dua elemen unik). Karena a ≠ b, setidaknya ada satu bit dalam a ^ b yang bernilai 1—temukan bit bernilai 1 terendah dari a ^ b menggunakan diff = xor_all & (-xor_all).
Bit ini bernilai 1 tepat pada salah satu dari a atau b. Kelompokkan semua bilangan menjadi dua kelompok berdasarkan apakah bit tersebut bernilai 1. Lakukan XOR pada setiap kelompok secara terpisah—elemen-elemen berpasangan saling membatalkan, sehingga a tersisa dalam satu kelompok dan b dalam kelompok lainnya.
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]Menemukan Bilangan yang Hilang dengan XOR
Masalah Bilangan yang Hilang (LeetCode 268): jika diberikan sebuah larik berisi n bilangan berbeda dari 0 hingga n, temukan bilangan yang hilang. Lakukan XOR terhadap semua bilangan dalam larik bersama semua bilangan dari 0 hingga n. Pasangan-pasangan saling membatalkan, sehingga bilangan yang hilang tersisa. Cara ini memberikan waktu O(n) dan ruang O(1).
Alternatifnya, gunakan rumus jumlah aritmetika: expected = n*(n+1)//2, lalu kurangi jumlah sebenarnya. Kedua pendekatan memiliki waktu O(n) dan ruang O(1). XOR lebih tangguh karena menghindari kemungkinan luapan bilangan bulat dalam bahasa pemrograman yang menggunakan bilangan bulat dengan lebar tetap.
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 untuk Menukar Tanpa Variabel Sementara
XOR memungkinkan penukaran dua variabel tanpa variabel sementara. Caranya adalah a ^ b ^ a = b dan a ^ b ^ b = a. Terapkan tiga penugasan XOR secara berurutan: a ^= b, lalu b ^= a, kemudian a ^= b. Setelah ketiganya, a menyimpan nilai awal b dan b menyimpan nilai awal a.
Catatan penting: cara ini gagal jika a dan b merujuk ke lokasi memori yang sama (yaitu jika keduanya adalah variabel yang sama). Dalam kasus tersebut, a ^= a mengatur a menjadi 0 dan nilainya hilang. Dalam Python, pembongkaran tuple (a, b = b, a) lebih aman dan lebih jelas. Penukaran XOR terutama berguna dalam konteks C atau sistem tertanam yang tidak memiliki memori tambahan.
# 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 dalam Pencincangan dan Nilai Pemeriksa
XOR adalah komponen pembangun umum dalam nilai pemeriksa dan pemeriksaan paritas. Melakukan XOR terhadap semua byte dalam sebuah blok data menghasilkan nilai pemeriksa satu byte. Jika satu bit berubah selama transmisi, nilai pemeriksa berubah sehingga kesalahan terdeteksi. Cara ini lebih sederhana daripada CRC, tetapi mendeteksi semua kesalahan satu bit.
XOR juga digunakan dalam paritas RAID-5: untuk tiga kandar, simpan XOR data dari dua kandar pada kandar ketiga. Jika satu kandar gagal, lakukan XOR terhadap dua kandar yang tersisa untuk merekonstruksi data yang hilang. Ini persis logika Angka Tunggal secara terbalik—kandar paritas adalah “elemen unik” yang menyandikan apa yang saling membatalkan ketika ketiganya dikenai 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 dan Masalah Himpunan Bagian
XOR muncul dalam masalah himpunan bagian ketika Anda perlu menghitung XOR semua himpunan bagian. Wawasan penting: untuk n elemen, setiap elemen muncul tepat 2^(n-1) kali dalam himpunan bagian. Jika n > 1, setiap elemen muncul dalam jumlah himpunan bagian yang genap, sehingga kontribusi XOR-nya saling membatalkan. XOR dari semua hasil XOR himpunan bagian adalah 0 untuk n > 1.
Untuk n == 1, satu-satunya himpunan bagian tak kosong adalah elemen itu sendiri, sehingga XOR semua himpunan bagian adalah elemen tersebut. Jenis penalaran ini—menggunakan sifat XOR dan pencacahan—diuji dalam masalah manipulasi bit tingkat lanjut.
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}')Pola Wawancara: XOR untuk Keunikan
Kenali pola XOR untuk keunikan ketika sebuah masalah menyatakan: ‘setiap elemen muncul k kali kecuali satu elemen yang muncul m kali, dengan m modulo k ≠ 0’. Untuk k=2, m=1 (Angka Tunggal I): lakukan XOR terhadap semua elemen. Untuk k=3, m=1 (Angka Tunggal II): hitung bit modulo 3. Untuk k=2, m=1 dengan dua elemen unik (Angka Tunggal III): lakukan XOR, lalu pisahkan berdasarkan bit berbeda terendah.
Pendekatan umum untuk k sembarang adalah menghitung total kemunculan setiap bit, lalu mengambil sisa pembagian terhadap k. Jika hitungannya tidak nol, bit tersebut termasuk dalam elemen unik. Cara ini menghasilkan algoritme O(32n) = O(n) dengan ruang O(1) untuk k apa pun.
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)) # 7Masalah Wawancara Umum tentang XOR
Di luar keluarga angka tunggal, XOR muncul dalam masalah-masalah yang sering ditanyakan berikut:
- Temukan Perbedaannya (LC 389): lakukan XOR terhadap semua karakter dari dua untai teks; karakter tambahan akan tersisa
- Jarak Hamming (LC 461): lakukan XOR terhadap dua bilangan, lalu hitung bit bernilai 1 dalam hasilnya
- Jarak Hamming Total (LC 477): hitung angka 0 dan 1 pada setiap posisi bit di seluruh pasangan
- Kueri XOR pada Sublarik (LC 1310): gunakan larik XOR awalan untuk kueri rentang
Dalam setiap kasus, sifat pembatalan XOR menghilangkan redundansi dan mengurangi solusi paksa O(n²) menjadi O(n).
# 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]]))Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini, Anda mempelajari: sifat invers terhadap dirinya sendiri dari XOR (a ^ a = 0) menyebabkan elemen berpasangan saling membatalkan ketika semua bilangan dikenai XOR, sehingga hanya menyisakan elemen unik, Angka Tunggal II menggunakan penghitungan bit modulo 3, sedangkan Angka Tunggal III memisahkan elemen berdasarkan bit berbeda terendah, dan XOR juga menyelesaikan masalah bilangan yang hilang, menemukan perbedaan, jarak Hamming, serta kueri XOR rentang. Selanjutnya, kita akan membahas mask bit untuk mengatur, menghapus, membalik, dan memeriksa bit satu per satu.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Single Number dan Sifat XOR” gratis?
Ya — teks lengkap “Single Number dan Sifat XOR” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Single Number dan Sifat XOR”?
Gunakan sifat invers-sendiri XOR untuk menemukan satu elemen yang muncul sekali dalam daftar, sementara semua elemen lain muncul dua kali, lalu kembangkan ke single-number-II dan III Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Single Number dan Sifat XOR” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Operator Bitwise: AND, OR, XOR, NOT, Pergeseran
- Single Number dan Sifat XOR
- Masker Bit: Set, Clear, Toggle, Check
- Menghitung Bit, Angka yang Hilang, dan Membalik Bit