Aller au contenu

E03 - XOR⚓︎

Le problème

XOR

Indices⚓︎

Nous verrons plusieurs méthodes de résolution, avec différentes complexités.

  • La meilleure utilise l'opérateur XOR, le ou exclusif bit-à-bit ; difficile à inventer vous-même.
  • Cependant, vous trouverez une méthode facile en triant le tableau des nombres...

Solution⚓︎

Basique⚓︎

🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2013/semifinal/xor
"""

def unique(nombres: list[int]) -> int:
    """Renvoie l'élément unique d'une liste de `nombres`,
       quand les autres sont en double.

    >>> unique([18, 42, 18])
    42

    >>> unique([1, 18, 42, 18, 1])
    42

    """
    nb_tries = sorted(nombres) # une copie triée
    nb_tries.append(1_000_001) # on ajoute un dernier pour avoir un nombre pair
    # 1,1,  3,3,  5,5,  7,8,  8,9,  9,10,  10,10 ...
    # le premier couple distinct indique l'élément unique ; à gauche
    n = len(nb_tries)
    for i in range(0, n, 2):
        if nb_tries[i] != nb_tries[i+1]:
            return nb_tries[i]


import doctest
doctest.testmod()

effectif = int(input())
nombres = list(map(int, input().split()))

print(unique(nombres))

Smart⚓︎

On utilise la propriété de XOR, le ou exclusif bit-à-bit.

Cet opérateur binaire est :

  • commutatif : \(a \text{ XOR } b = b \text{ XOR } a\)
  • associatif : \((a \text{ XOR } b) \text{ XOR } c = a \text{ XOR } (b \text{ XOR } c)\)
  • et on a : \(a \text{ XOR } a = 0\)
  • et aussi : \(a \text{ XOR } 0 = a\)

De sorte que dans une liste où tous les nombres sont en doublon, un \(\text{XOR}\) de tous les nombres conduit à zéro, en effet on \(\text{XOR}\) dans l'ordre que l'on veut, le résultat.

Le dernier nombre seul, en appliquant le dernier \(\text{XOR}\) avec zéro reste inchangé.

D'après les propriétés de \(\text{XOR}\), on peut faire les opérations dans l'ordre de la liste.

🐍 Script Python
effectif = int(input())
nombres = map(int, input().split()) 

unique = 0
for n in nombres:
    unique = unique ^ n
    # unique ^= n # équivalent

print(unique)

Et avec un style fonctionnel, on a :

🐍 Script Python
from functools import reduce
from operator import xor

effectif = int(input())
nombres = map(int, input().split())

unique = reduce(xor, nombres)

print(unique)

On pourrait même remplacer les trois dernières lignes par :

🐍 Script Python
print(reduce(xor, map(int, input().split())))

Mais le code est plus lisible sur trois lignes, et tout aussi efficace.