E03 - XOR⚓︎
Le problème
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.