PricingLoginStart free
Forberedelse til kodeintervjuer · leksjon

Single Number og XOR-egenskaper

Bruk XORs selv-inverse egenskap til å finne det ene elementet som forekommer én gang i en liste der alle andre forekommer to ganger, og utvid deretter til «single-number-II» og «single-number-III».

Leksjon 2 av 413 trinn

Single Number og XOR-egenskaper er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Problemet med Single Number

Problemet Single Number (LeetCode 136) spør: Gitt en array der hvert element forekommer nøyaktig to ganger, bortsett fra ett, skal elementet som bare forekommer én gang finnes. Kravet om O(n)-tid og O(1)-plass utelukker hashtabeller (O(n)-plass) og sortering (O(n log n)-tid eller O(n)-plass for sorteringen).

Den elegante løsningen bruker XOR. XOR alle elementene sammen. Siden identiske elementer kansellerer hverandre (a ^ a = 0), og XOR er kommutativ og assosiativ, forsvinner alle parvise elementer, slik at bare det enkeltstående elementet blir igjen. Dette er en av de mest tilfredsstillende O(n)/O(1)-løsningene innen konkurranseprogrammering.

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

Hvorfor XOR fungerer: tre nøkkelegenskaper

XORs styrke skyldes at tre algebraiske egenskaper virker sammen:

  • Selvinvers: a ^ a = 0 — identiske verdier kansellerer hverandre
  • Identitet: a ^ 0 = a — XOR med null endrer ikke verdiene
  • Kommutativitet og assosiativitet: rekkefølgen spiller ingen rolle, og grupperingene spiller ingen rolle

Disse tre egenskapene gjør samlet at XOR over en multimengde reduserer alle elementer som forekommer et partall antall ganger, til 0, slik at bare elementer som forekommer et oddetall antall ganger, blir igjen. I Single Number I forekommer nøyaktig ett element én gang (oddetall), og det er derfor XOR-resultatet.

# 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

Gå gjennom Single Number

La oss gå gjennom [4, 1, 2, 1, 2] trinn for trinn for å se kanselleringen i praksis. Vi XOR-er alle elementene: 4 ^ 1 ^ 2 ^ 1 ^ 2. Siden XOR er kommutativ, kan vi omorganisere uttrykket til (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4. Parene kansellerer hverandre, og bare 4 blir igjen.

I den faktiske algoritmen omorganiserer vi ikke elementene — vi XOR-er fra venstre mot høyre. Sluttresultatet blir likevel det samme, fordi kommutativitet og assosiativitet garanterer at rekkefølgen ikke påvirker resultatet. Parene kan grupperes mentalt hvor som helst, og de kansellerer alltid hverandre.

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: Hvert element forekommer tre ganger

Single Number II (LeetCode 137): hvert element forekommer tre ganger, bortsett fra ett som forekommer én gang. XOR alene fungerer ikke — parene kansellerer ikke lenger når de forekommer tre ganger. I stedet teller vi hvor mange ganger hver bit forekommer på tvers av alle tallene. Hvis en bit forekommer i målelementet, bidrar den med 1; i elementer som forekommer tre ganger, bidrar den med 3. Ta antall modulo 3 for hver bit for å isolere bitene i målelementet.

Dette kan simuleres med to heltallsvariabler, ones og twos, som fungerer som en teller på bitnivå modulo 3. Dette er en digital-logisk tilnærming: ones inneholder biter som er sett et oddetall antall ganger modulo 2, mens twos inneholder biter som er sett to ganger 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]))  # 3

Single Number III: To elementer forekommer én gang

Single Number III (LeetCode 260): to elementer forekommer én gang hver, mens alle andre forekommer to ganger. XOR alle elementene for å få a ^ b (XOR-en av de to unike elementene). Siden a ≠ b, er minst én bit i a ^ b 1 — finn den laveste satte biten i a ^ b ved å bruke diff = xor_all & (-xor_all).

Denne biten er 1 i nøyaktig én av a eller b. Del alle tallene inn i to grupper basert på om denne biten er satt. XOR hver gruppe separat — de parvise elementene kansellerer hverandre, slik at a blir igjen i den ene gruppen og b i den andre.

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]

Finne det manglende tallet med XOR

Problemet Missing Number (LeetCode 268): Gitt en array med n ulike tall fra 0 til n skal det manglende tallet finnes. XOR alle tallene i arrayen med alle tallene fra 0 til n. Parene kansellerer hverandre, slik at det manglende tallet blir igjen. Dette gir O(n)-tid og O(1)-plass.

Alternativt kan den aritmetiske summen brukes: expected = n*(n+1)//2, og deretter kan den faktiske summen trekkes fra. Begge metodene har O(n)/O(1). XOR er mer robust fordi metoden unngår potensielt heltallsoverløp i språk med heltall med fast bredde.

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-bytte uten midlertidig variabel

XOR gjør det mulig å bytte om to variabler uten en midlertidig variabel. Trikset er at a ^ b ^ a = b og a ^ b ^ b = a. Utfør tre XOR-tildelinger i rekkefølge: a ^= b, deretter b ^= a, og til slutt a ^= b. Etter alle tre inneholder a den opprinnelige verdien til b, og b inneholder den opprinnelige verdien til a.

Viktig forbehold: Dette trikset fungerer ikke hvis a og b refererer til samme minneplass (det vil si hvis de er den samme variabelen). I så fall setter a ^= a a til 0, og verdien går tapt. I Python er tuple-unpacking (a, b = b, a) tryggere og tydeligere. XOR-bytte er hovedsakelig nyttig i C- og innebygde systemer der det ikke finnes ekstra minne.

# 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 i hashing og kontrollsummer

XOR er en vanlig byggestein i kontrollsummer og paritetssjekker. XOR-operasjonen på alle byte i en datablokk gir en kontrollsum på én byte. Hvis én enkelt bit endres under overføringen, endres kontrollsummen, og feilen oppdages. Dette er enklere enn CRC, men fanger opp alle enkeltbitfeil.

XOR brukes også i RAID-5-paritet: For tre disker lagres XOR-en av dataene på to disker på den tredje. Hvis én disk svikter, kan de to gjenværende diskene XOR-es for å gjenopprette de tapte dataene. Dette er nøyaktig Single Number-logikken i omvendt retning — paritetsdisken er det «unike elementet» som koder hva som kanselleres når alle tre XOR-es.

# 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 og delmengdeproblemer

XOR dukker opp i delmengdeproblemer når det er nødvendig å beregne XOR-en av alle delmengder. En viktig innsikt er at hvert element forekommer i nøyaktig 2^(n-1) delmengder for n elementer. Hvis n > 1, forekommer hvert element i et partall antall delmengder, og XOR-bidraget kanselleres derfor. XOR-en av alle XOR-resultatene for delmengdene er 0 når n > 1.

Når n == 1, er den eneste ikke-tomme delmengden selve elementet, så XOR-en av alle delmengdene er dette elementet. Denne typen resonnement — der XOR-egenskaper kombineres med telling — testes i avanserte problemer innen bitmanipulering.

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}')

Intervjumønster: XOR for unikhet

Gjenkjenn mønsteret XOR for unikhet når en oppgave sier: «alle elementer forekommer k ganger, bortsett fra ett som forekommer m ganger, der m mod k != 0». For k=2, m=1 (Single Number I): XOR alle elementene. For k=3, m=1 (Single Number II): tell biter modulo 3. For k=2, m=1 med to unike elementer (Single Number III): XOR først, og del deretter etter den laveste biten som er forskjellig.

Den generelle fremgangsmåten for en vilkårlig k er å telle det totale antallet forekomster av hver bit og ta modulo k. Hvis antallet ikke er null, tilhører biten det unike elementet. Dette gir en O(32n) = O(n)-algoritme med O(1)-plass for enhver k.

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

Vanlige XOR-problemer i jobbintervjuer

Utover Single Number-familien brukes XOR i disse ofte stilte problemene:

  • Find the Difference (LC 389): XOR alle tegnene i begge strengene; det ekstra tegnet blir igjen
  • Hamming Distance (LC 461): XOR to tall og tell 1-bitene i resultatet
  • Total Hamming Distance (LC 477): tell 0-ere og 1-ere på hver bitposisjon på tvers av alle par
  • XOR Queries of a Subarray (LC 1310): bruk en prefiks-XOR-array for intervallspørringer

I hvert tilfelle eliminerer XORs kanselleringsegenskap overflødighet og reduserer en O(n²)-brute force-løsning til 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]]))

Hurtigsjekk

Test forståelsen av konseptene innen Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

I denne leksjonen lærte De: at XORs selvinverse egenskap (a ^ a = 0) gjør at parvise elementer kansellerer hverandre, slik at bare det unike elementet blir igjen når alle tall XOR-es sammen, at Single Number II bruker bittelling modulo 3, mens Single Number III deler elementene etter den laveste biten som er forskjellig, og at XOR også løser Missing Number, Find the Difference, Hamming-avstand og XOR-spørringer på intervaller. Deretter ser vi på bitmasker for å sette, nullstille, veksle og kontrollere enkeltbiter.

Gratis å komme i gang

Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs
90
Leksjoner
360
Start læringen gratisSe hele kurset

Ofte stilte spørsmål

Er leksjonen «Single Number og XOR-egenskaper» gratis?

Ja – hele teksten i «Single Number og XOR-egenskaper» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Hva lærer jeg i «Single Number og XOR-egenskaper»?

Bruk XORs selv-inverse egenskap til å finne det ene elementet som forekommer én gang i en liste der alle andre forekommer to ganger, og utvid deretter til «single-number-II» og «single-number-III». Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?

Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.

Hvor lang tid tar leksjonen «Single Number og XOR-egenskaper»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?

Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

  1. Bitvise operatorer: AND, OR, XOR, NOT og skift
  2. Single Number og XOR-egenskaper
  3. Bitmasker: Sett, fjern, inverter og kontroller
  4. Tell biter, manglende tall og inverterte biter
← Tilbake til Forberedelse til kodeintervjuer