Tek Sayı ve XOR Özellikleri
Diğer tüm öğelerin iki kez göründüğü bir listede yalnızca bir kez görünen öğeyi bulmak için XOR’un kendi tersini alma özelliğini kullanın; ardından bunu tek-sayı-II ve III’e genişletin.
Tek Sayı ve XOR Özellikleri, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Tek Sayı Problemi
Tek Sayı problemi (LeetCode 136) şunu sorar: her öğenin tam iki kez göründüğü, yalnızca bir öğenin bir kez göründüğü bir dizi verildiğinde, yalnızca bir kez görünen öğeyi bulun. O(n) zaman ve O(1) alan kısıtları, karma tablolarını (O(n) alan) ve sıralamayı (sıralama için O(n log n) zaman veya O(n) alan) eler.
Zarif çözümde XOR kullanılır. Tüm öğelere XOR uygulayın. Aynı öğeler birbirini götürdüğünden (a ^ a = 0) ve XOR işlemi değişme ile birleşme özelliklerine sahip olduğundan, eşleşen tüm öğeler yok olur ve geriye yalnızca tek öğe kalır. Bu, rekabetçi programlamadaki en tatmin edici O(n)/O(1) çözümlerden biridir.
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])) # 1XOR Neden Çalışır: Üç Temel Özellik
XOR işleminin gücü, birlikte çalışan üç cebirsel özellikten kaynaklanır:
- Kendine ters olma:
a ^ a = 0— aynı değerler birbirini götürür - Etkisizlik:
a ^ 0 = a— sıfır ile XOR uygulamak değerleri değiştirmez - Değişme ve birleşme: sıra önemli değildir, gruplama önemli değildir
Bu üç özellik birlikte, bir çoklu kümedeki çift sayıda görünen tüm öğeleri 0'a indirger ve yalnızca tek sayıda görünen öğeleri bırakır. Tek Sayı I için tam olarak bir öğe bir kez, yani tek sayıda görünür; dolayısıyla bu öğe XOR sonucudur.
# 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 resultTek Sayı Üzerinde Adım Adım İnceleme
İptalin nasıl gerçekleştiğini görmek için [4, 1, 2, 1, 2] dizisini adım adım inceleyelim. Tüm öğelere XOR uygularız: 4 ^ 1 ^ 2 ^ 1 ^ 2. XOR değişme özelliğine sahip olduğundan ifadeyi (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4 biçiminde yeniden sıralayabiliriz. Çiftler birbirini götürür ve yalnızca 4 kalır.
Gerçek algoritmada yeniden sıralama yapmayız; öğelere soldan sağa XOR uygularız. Ancak değişme ve birleşme özellikleri sıranın sonucu etkilememesini garanti ettiğinden nihai sonuç aynıdır. Çiftleri zihninizde istediğiniz yerde gruplayabilirsiniz; hepsi birbirini götürür.
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')Tek Sayı II: Her Öğe Üç Kez Görünür
Tek Sayı II (LeetCode 137): Bir öğe bir kez görünürken diğer her öğe üç kez görünür. XOR tek başına işe yaramaz; çünkü çiftler artık üçlüler içinde birbirini götürmez. Bunun yerine, tüm sayılardaki her bitin kaç kez göründüğünü sayarız. Bir bit aranan öğede varsa katkısı 1, üçlü öğelerde ise 3 olur. Aranan öğenin bitlerini ayırmak için her bitin sayımını 3'e göre mod alırız.
Bunu, 3'e göre modüler bir bit düzeyi sayacı gibi çalışan iki tamsayı değişkeniyle, ones ve twos ile benzetebiliriz. Bu, sayısal mantık yaklaşımıdır: ones, tek sayıda görülen bitleri 2'ye göre modüler olarak tutar; twos ise iki kez görülen bitleri 3'e göre modüler olarak tutar.
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])) # 3Tek Sayı III: İki Öğe Bir Kez Görünür
Tek Sayı III (LeetCode 260): İki öğenin her biri bir kez, diğer tüm öğelerin her biri iki kez görünür. a ^ b elde etmek için tüm öğelere XOR uygulayın; bu, iki tekil öğenin XOR'udur. a ≠ b olduğundan, a ^ b içinde en az bir bit 1'dir. diff = xor_all & (-xor_all) kullanarak a ^ b içindeki en düşük konumdaki 1 bitini bulun.
Bu bit, a veya b'den yalnızca birinde 1'dir. Tüm sayıları, bu bitin 1 olup olmamasına göre iki gruba ayırın. Her gruba ayrı ayrı XOR uygulayın; eşleşen öğeler birbirini götürür ve bir grupta a, diğer grupta b kalır.
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]Eksik Sayıyı XOR ile Bulma
Eksik Sayı problemi (LeetCode 268): 0 ile n arasındaki birbirinden farklı n sayıdan oluşan bir dizi verildiğinde, eksik olanı bulun. Dizideki tüm sayılara 0 ile n arasındaki tüm sayılara XOR uygulayın. Çiftler birbirini götürür ve geriye eksik sayı kalır. Böylece O(n) zaman ve O(1) alan elde edilir.
Alternatif olarak aritmetik toplam formülünü kullanabilirsiniz: expected = n*(n+1)//2; ardından gerçek toplamı çıkarın. Her iki yaklaşım da O(n)/O(1)'dir. XOR, sabit genişlikli tamsayılar kullanan dillerde olası tamsayı taşmalarını önlediği için daha güvenilirdir.
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}')Geçici Değişken Olmadan XOR ile Takas
XOR, iki değişkeni geçici bir değişken kullanmadan takas etmenizi sağlar. Bunun temelinde a ^ b ^ a = b ve a ^ b ^ b = a eşitlikleri vardır. Sırasıyla üç XOR ataması yapın: a ^= b, ardından b ^= a, sonra da a ^= b. Üçünün ardından a, başlangıçtaki b değerini; b ise başlangıçtaki a değerini tutar.
Önemli bir uyarı: a ve b aynı bellek konumuna başvuruyorsa, yani aynı değişkense, bu yöntem başarısız olur. Bu durumda a ^= a, a'yı 0 yapar ve değer kaybolur. Python'da demet açma (a, b = b, a) daha güvenli ve anlaşılırdır. XOR ile takas, temel olarak ek belleğin bulunmadığı C/gömülü sistem bağlamlarında kullanışlıdır.
# 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}')Karma ve Sağlama Toplamlarında XOR
XOR, sağlama toplamlarında ve eşlik denetimlerinde yaygın bir yapı taşıdır. Bir veri bloğundaki tüm baytlara XOR uygulamak tek baytlık bir sağlama toplamı üretir. İletim sırasında tek bir bit değişirse sağlama toplamı değişir ve hata algılanır. Bu yöntem CRC'den daha basittir, ancak tüm tek bitlik hataları yakalar.
XOR, RAID-5 eşliğinde de kullanılır: üç sürücü için, iki sürücünün verilerinin XOR sonucunu üçüncü sürücüde saklayın. Bir sürücü arızalanırsa kayıp veriyi yeniden oluşturmak için kalan iki sürücüye XOR uygulayın. Bu, Tek Sayı mantığının tersine uygulanmasıdır; eşlik sürücüsü, üçünün tümüne XOR uygulandığında hangi bilgilerin yok olduğunu kodlayan 'tekil öğedir'.
# 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 ve Alt Küme Problemleri
Tüm alt kümelerin XOR'u hesaplanmak istendiğinde, alt küme problemlerinde XOR karşımıza çıkar. Önemli bir gözlem şudur: n öğe için her öğe tam olarak 2^(n-1) alt kümede bulunur. n > 1 ise her öğe çift sayıda alt kümede bulunur; bu nedenle XOR katkısı yok olur. Tüm alt kümelerin XOR sonuçlarının XOR'u, n > 1 için 0'dır.
n == 1 için boş olmayan tek alt küme öğenin kendisidir; dolayısıyla tüm alt kümelerin XOR'u o öğedir. XOR özelliklerini saymayla birlikte kullanan bu tür akıl yürütmeler, ileri düzey bit işlemi problemlerinde sınanır.
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}')Mülakat Kalıbı: Tekillik için XOR
Bir problem şöyle diyorsa tekillik için XOR kalıbını tanıyın: 'bir öğe m kez görünürken diğer her öğe k kez görünür ve m mod k != 0'dır'. k=2, m=1 için (Tek Sayı I) tüm öğelere XOR uygulayın. k=3, m=1 için (Tek Sayı II) bitleri sayıp 3'e göre mod alın. İki tekil öğenin bulunduğu k=2, m=1 durumu için (Tek Sayı III) önce XOR uygulayın, ardından en düşük farklı bite göre ayırın.
Herhangi bir k için genel yaklaşım, her bitin toplam görülme sayısını hesaplayıp k'ye göre mod almaktır. Sayım sıfır değilse, o bit tekil öğeye aittir. Böylece herhangi bir k için O(32n) = O(n) zaman ve O(1) alan kullanan bir algoritma elde edilir.
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)) # 7Yaygın XOR Mülakat Problemleri
Tek Sayı ailesinin ötesinde, XOR şu sık sorulan problemlerde de karşımıza çıkar:
- Farkı Bul (LC 389): Her iki dizenin tüm karakterlerine XOR uygulayın; fazladan karakter kalır
- Hamming Uzaklığı (LC 461): İki sayıya XOR uygulayın ve sonuçtaki 1 bitlerini sayın
- Toplam Hamming Uzaklığı (LC 477): Tüm çiftlerde her bit konumundaki 0'ları ve 1'leri sayın
- Bir Alt Dizinin XOR Sorguları (LC 1310): aralık sorguları için ön ek XOR dizisini kullanın
Her durumda XOR'un iptal özelliği tekrarı ortadan kaldırır ve O(n²) kaba kuvvet çözümünü O(n)'e indirger.
# 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]]))Hızlı Kontrol
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarına ilişkin anlayışınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: XOR işleminin kendine ters olma özelliği (a ^ a = 0), tüm sayılara XOR uygulandığında eşleşen öğelerin yok olmasını ve yalnızca tekil öğenin kalmasını sağlar; Tek Sayı II, bitleri 3'e göre modüler olarak sayarken Tek Sayı III, öğeleri en düşük farklı bite göre ayırır; ayrıca XOR, eksik sayıyı bulma, farkı bulma, Hamming uzaklığı ve aralık XOR sorgularını da çözer. Sırada tek tek bitleri ayarlamak, temizlemek, terslemek ve denetlemek için bit maskelerini inceleyeceğiz.
Sıkça Sorulan Sorular
“Tek Sayı ve XOR Özellikleri” dersi ücretsiz mi?
Evet — “Tek Sayı ve XOR Özellikleri” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Tek Sayı ve XOR Özellikleri” dersinde ne öğreneceğim?
Diğer tüm öğelerin iki kez göründüğü bir listede yalnızca bir kez görünen öğeyi bulmak için XOR’un kendi tersini alma özelliğini kullanın; ardından bunu tek-sayı-II ve III’e genişletin. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“Tek Sayı ve XOR Özellikleri” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Bit Düzeyi İşleçler: AND, OR, XOR, NOT ve Kaydırmalar
- Tek Sayı ve XOR Özellikleri
- Bit Maskeleri: Ayarla, Temizle, Değiştir, Denetle
- Bitleri Sayma, Eksik Sayı ve Bitleri Ters Çevirme