PricingLoginStart free
DSA Interview Prep · Leçon

Nombre unique et propriétés de XOR

Utilisez la propriété d’inverse propre à XOR pour trouver l’unique élément apparaissant une fois dans une liste où tous les autres apparaissent deux fois, puis étendez la méthode à single-number-II et III.

Leçon 2 sur 413 étapes

Nombre unique et propriétés de XOR est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.

Le problème du nombre unique

Le problème du nombre unique (LeetCode 136) demande : étant donné un tableau dans lequel chaque élément apparaît exactement deux fois, sauf un, trouvez l’élément qui n’apparaît qu’une seule fois. La contrainte de temps O(n) et d’espace O(1) exclut les tables de hachage (espace O(n)) et le tri (temps O(n log n) ou espace O(n) pour le tri).

La solution élégante utilise XOR. Combinez tous les éléments par XOR. Comme les éléments identiques s’annulent (a ^ a = 0) et que XOR est commutatif et associatif, toutes les paires disparaissent et il ne reste que l’élément unique. C’est l’une des solutions O(n)/O(1) les plus satisfaisantes de toute la programmation compétitive.

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

Pourquoi XOR fonctionne : trois propriétés clés

La puissance de XOR vient de trois propriétés algébriques qui agissent ensemble :

  • Auto-inverse : a ^ a = 0 — les valeurs identiques s’annulent
  • Élément neutre : a ^ 0 = a — combiner une valeur avec zéro par XOR ne la modifie pas
  • Commutativité et associativité : l’ordre et les regroupements n’ont aucune importance

Ensemble, ces trois propriétés signifient que le XOR d’un multiensemble ramène à 0 tous les éléments apparaissant un nombre pair de fois, en ne laissant que ceux apparaissant un nombre impair de fois. Dans le problème du nombre unique I, exactement un élément apparaît une fois, donc un nombre impair de fois : c’est le résultat du 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 result

Suivi pas à pas du nombre unique

Suivons [4, 1, 2, 1, 2] étape par étape pour observer l’annulation. Nous combinons tous les éléments par XOR : 4 ^ 1 ^ 2 ^ 1 ^ 2. Comme XOR est commutatif, réorganisons l’expression ainsi : (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4. Les paires s’annulent et seul 4 reste.

Dans l’algorithme réel, nous ne réorganisons pas les éléments : nous appliquons XOR de gauche à droite. Le résultat final reste toutefois le même, car la commutativité et l’associativité garantissent que l’ordre n’influence pas le résultat. Vous pouvez regrouper mentalement les paires où vous le souhaitez : elles s’annuleront toutes.

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

Nombre unique II : chaque élément apparaît trois fois

Nombre unique II (LeetCode 137) : chaque élément apparaît trois fois, sauf un qui apparaît une seule fois. XOR seul ne fonctionne pas : les paires ne s’annulent plus par groupes de trois. Nous comptons plutôt le nombre d’apparitions de chaque bit dans tous les nombres. Si un bit apparaît dans l’élément recherché, il contribue pour 1 ; dans les éléments apparaissant trois fois, il contribue pour 3. Prenez le compte modulo 3 pour chaque bit afin d’isoler les bits de l’élément recherché.

Nous pouvons simuler cela avec deux variables entières, ones et twos, qui jouent le rôle d’un compteur au niveau des bits modulo 3. Il s’agit d’une approche de logique numérique : ones contient les bits vus un nombre impair de fois modulo 2, tandis que twos contient les bits vus deux fois 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

Nombre unique III : deux éléments apparaissent une seule fois

Nombre unique III (LeetCode 260) : deux éléments apparaissent chacun une seule fois ; tous les autres apparaissent deux fois. Combinez tous les éléments par XOR pour obtenir a ^ b, c’est-à-dire le XOR des deux éléments uniques. Comme a ≠ b, au moins un bit de a ^ b vaut 1 : trouvez le bit de poids le plus faible à 1 de a ^ b à l’aide de diff = xor_all & (-xor_all).

Ce bit vaut 1 dans exactement l’un des deux éléments a et b. Répartissez tous les nombres en deux groupes selon que ce bit vaut 1 ou non. Effectuez un XOR séparément sur chaque groupe : les éléments appariés s’annulent, laissant a dans un groupe et b dans l’autre.

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]

Trouver le nombre manquant avec XOR

Le problème du nombre manquant (LeetCode 268) consiste, étant donné un tableau de n nombres distincts compris entre 0 et n, à trouver celui qui manque. Combinez par XOR tous les nombres du tableau avec tous les nombres de 0 à n. Les paires s’annulent et le nombre manquant reste seul. Cette approche utilise un temps O(n) et un espace O(1).

Vous pouvez aussi utiliser la formule de la somme arithmétique : expected = n*(n+1)//2, puis soustraire la somme réelle. Les deux approches sont en O(n)/O(1). XOR est plus robuste, car il évite les dépassements de capacité potentiels dans les langages utilisant des entiers de largeur fixe.

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

Échanger avec XOR sans variable temporaire

XOR permet d’échanger deux variables sans variable temporaire. L’astuce repose sur le fait que a ^ b ^ a = b et a ^ b ^ b = a. Effectuez trois affectations XOR successives : a ^= b, puis b ^= a, puis a ^= b. Après ces trois opérations, a contient la valeur initiale de b et b contient la valeur initiale de a.

Attention : cette astuce échoue si a et b font référence au même emplacement mémoire, c’est-à-dire s’il s’agit de la même variable. Dans ce cas, a ^= a affecte 0 à a et la valeur est perdue. En Python, le déballage de tuple (a, b = b, a) est plus sûr et plus clair. L’échange par XOR est surtout utile dans les contextes C ou embarqués ne disposant d’aucune mémoire supplémentaire.

# 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 dans le hachage et les sommes de contrôle

XOR est un élément courant des sommes de contrôle et des contrôles de parité. Effectuer un XOR sur tous les octets d’un bloc de données produit une somme de contrôle d’un octet. Si un seul bit s’inverse pendant la transmission, la somme de contrôle change, ce qui permet de détecter l’erreur. Cette méthode est plus simple que CRC, mais détecte toutes les erreurs portant sur un seul bit.

XOR est également utilisé pour la parité de RAID-5 : pour trois disques, stockez sur le troisième le XOR des données des deux premiers. Si un disque tombe en panne, effectuez un XOR sur les deux disques restants pour reconstruire les données perdues. Il s’agit exactement de la logique du nombre unique appliquée à l’envers : le disque de parité est l’« élément unique » qui encode ce qui s’annule lorsque les trois disques sont combinés par 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 et problèmes de sous-ensembles

XOR intervient dans les problèmes de sous-ensembles lorsque vous devez calculer le XOR de tous les sous-ensembles. Une observation essentielle : pour n éléments, chaque élément apparaît dans exactement 2^(n-1) sous-ensembles. Si n > 1, chaque élément apparaît un nombre pair de fois, donc sa contribution au XOR s’annule. Le XOR de tous les XOR de sous-ensembles vaut 0 pour n > 1.

Pour n == 1, le seul sous-ensemble non vide est l’élément lui-même ; le XOR de tous les sous-ensembles est donc cet élément. Ce type de raisonnement, qui utilise les propriétés de XOR et le dénombrement, est mis à l’épreuve dans les problèmes avancés de manipulation des bits.

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

Schéma d’entretien : XOR et unicité

Reconnaissez le schéma « XOR pour l’unicité » lorsqu’un problème indique : « chaque élément apparaît k fois, sauf un qui apparaît m fois, avec m mod k ≠ 0 ». Pour k=2 et m=1 (nombre unique I), combinez tous les éléments par XOR. Pour k=3 et m=1 (nombre unique II), comptez les bits modulo 3. Pour k=2 et m=1 avec deux éléments uniques (nombre unique III), appliquez XOR, puis séparez les éléments selon le bit de poids le plus faible qui diffère.

L’approche générale pour un k quelconque consiste à compter le nombre total d’apparitions de chaque bit et à prendre le modulo k. Si le compte est non nul, ce bit appartient à l’élément unique. On obtient ainsi un algorithme O(32n) = O(n) utilisant un espace O(1), quel que soit 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

Problèmes d’entretien courants utilisant XOR

Au-delà de la famille des problèmes du nombre unique, XOR intervient dans les problèmes fréquemment posés suivants :

  • Trouver la différence (LC 389) : effectuez un XOR sur tous les caractères des deux chaînes ; le caractère supplémentaire subsiste
  • Distance de Hamming (LC 461) : effectuez un XOR sur deux nombres, puis comptez les bits à 1 du résultat
  • Distance de Hamming totale (LC 477) : comptez les 0 et les 1 à chaque position de bit sur toutes les paires
  • Requêtes XOR sur un sous-tableau (LC 1310) : utilisez un tableau de XOR préfixes pour les requêtes sur des intervalles

Dans chaque cas, la propriété d’annulation de XOR élimine la redondance et réduit une recherche exhaustive en O(n²) à 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]]))

Vérification rapide

Testez votre compréhension des concepts de « Structures de données & algorithmes — préparation aux entretiens de programmation » abordés dans cette leçon.

Réponds-y dans la leçon interactive

Récapitulatif de la leçon

Dans cette leçon, vous avez appris : la propriété d’auto-inversion de XOR (a ^ a = 0) entraîne l’annulation des éléments appariés, ne laissant que l’élément unique lorsque tous les nombres sont combinés par XOR, le nombre unique II utilise le comptage des bits modulo 3, tandis que le nombre unique III sépare les éléments selon le bit de poids le plus faible qui diffère, et XOR résout également les problèmes du nombre manquant, de la recherche de la différence, de la distance de Hamming et des requêtes XOR sur des intervalles. Ensuite, nous étudierons les masques de bits pour positionner, effacer, inverser et vérifier des bits individuels.

Gratuit pour commencer

Apprends Python avec un tuteur IA — gratuit

Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.

Cours
30
Leçons
120
Commencer gratuitementVoir le cours complet

Questions Fréquemment Posées

La leçon « Nombre unique et propriétés de XOR » est-elle gratuite ?

Oui — le texte complet de « Nombre unique et propriétés de XOR » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Nombre unique et propriétés de XOR » ?

Utilisez la propriété d’inverse propre à XOR pour trouver l’unique élément apparaissant une fois dans une liste où tous les autres apparaissent deux fois, puis étendez la méthode à single-number-II e… Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?

Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.

Combien de temps prend la leçon « Nombre unique et propriétés de XOR » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?

Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Opérateurs bit à bit : AND, OR, XOR, NOT et décalages
  2. Nombre unique et propriétés de XOR
  3. Masques binaires : définir, effacer, inverser et vérifier
  4. Compter les bits, nombre manquant et inversion des bits
← Retour à DSA Interview Prep