Descubra o Número Único em uma Lista: Soluções com e sem XOR

2024-06-18

DATE: 2024.06.18 LATENCY: -- STATUS: ONLINE

Encontrando o Número Único em uma Lista com e sem XOR

Em muitos problemas de programação, é comum lidar com listas onde todos os elementos, exceto um, aparecem exatamente duas vezes. Encontrar o número único pode ser uma tarefa interessante e desafiadora. Neste post, vamos explorar duas abordagens para resolver esse problema: uma usando o operador XOR e outra usando um dicionário para contar ocorrências.

Problema:

Dada uma lista de números onde cada número, exceto um, aparece exatamente duas vezes, encontre o número único.

Exemplo: Entrada: [4, 1, 2, 1, 2]
Saída: 4

Solução 1: Usando o Operador XOR

O operador XOR (ou exclusivo) é uma operação lógica que resulta em verdadeiro (ou 1) se e somente se um dos operandos for verdadeiro (ou 1), mas não ambos. Uma propriedade interessante do XOR é que A ^ A = 0 e A ^ 0 = A. Isso significa que quando você XOR todos os números da lista, os números que aparecem em pares se cancelam, e o número que aparece uma única vez permanece.

Implementação em Python:

def find_unique_number(nums):
    unique_number = 0
    for num in nums:
        unique_number ^= num
    return unique_number

# Exemplo de uso
nums = [4, 1, 2, 1, 2]
unique_number = find_unique_number(nums)
print(f"O número único é: {unique_number}")

Explicação:

Inicializamos unique_number com 0.
Iteramos sobre cada número na lista nums.
Aplicamos o operador XOR entre unique_number e o número atual.
Após a iteração, unique_number conterá o número que aparece apenas uma vez.

Solução 2: Usando um Dicionário para Contar Ocorrências

Outra abordagem eficiente é usar um dicionário (ou o objeto Counter da biblioteca collections) para contar a ocorrência de cada número na lista. Em seguida, identificamos o número que aparece apenas uma vez.

Implementação com Dicionário:

def find_unique_number(nums):
    count_dict = {}

    # Contar a ocorrência de cada número
    for num in nums:
        if num in count_dict:
            count_dict[num] += 1
        else:
            count_dict[num] = 1

    # Encontrar o número que aparece apenas uma vez
    for num, count in count_dict.items():
        if count == 1:
            return num

# Exemplo de uso
nums = [4, 1, 2, 1, 2]
unique_number = find_unique_number(nums)
print(f"O número único é: {unique_number}")

Explicação:

Criamos um dicionário count_dict para armazenar a contagem de cada número.
Iteramos sobre cada número na lista e atualizamos o dicionário com a contagem de ocorrências.
Iteramos sobre o dicionário para encontrar o número que aparece apenas uma vez.

Solução Alternativa com `Counter` da Biblioteca `collections`

A biblioteca collections oferece uma maneira conveniente de contar elementos usando Counter.

Implementação com Counter:

from collections import Counter

def find_unique_number(nums):
    # Contar a ocorrência de cada número usando Counter
    count = Counter(nums)

    # Encontrar o número que aparece apenas uma vez
    for num, freq in count.items():
        if freq == 1:
            return num

# Exemplo de uso
nums = [4, 1, 2, 1, 2]
unique_number = find_unique_number(nums)
print(f"O número único é: {unique_number}")

Conclusão

Ambas as abordagens apresentadas são eficientes e possuem complexidade de tempo O(n). A escolha entre usar XOR ou um dicionário depende do contexto e das preferências pessoais. O uso de XOR é elegante e usa constante espaço adicional, enquanto o uso de um dicionário é mais intuitivo e fácil de entender, especialmente para iniciantes.