Solução Número de Fora, por Pedro Racchetti
Conhecimentos utilizados:
- Representação binária de números
- Set
Para esse problema, analise primeiro o primeiro bit. Como existem $$n$$ números, de um intervalo de $$0$$ a $$n$$, podemos ver que, como $$floor((n + 1)/2)$$ dos números do intervalo são ímpares, se menos que essa quantidade de número da lista for ímpar, sabemos que o número de fora é impar, caso contrário ele é par. Podemos agora eliminar todos os índices com paridade contrária ao número de fora, dividindo o tamanho da lista por $$2$$
Perceba que um número é par se e somente se o $$0$$-ésimo bit dele for $$0$$. Perceba que o que foi dito acima também se aplica para todos os bits, podendo então se aplicar a ideia para o bit $$1$$ de todos os números que não foram eliminados, dividindo o tamanho da lista possível de números de fora por $$2$$. Fazendo isso sucessivamente, eventualmente chegaremos a resposta, já que saberemos todos os bits do número. Isso irá nos custar no máximo $$2 \cdotp n$$ perguntas já que $$n + n/2 + (n/2)/2 + ((n/2)/2)/2 … $$ é igual a $$n + n/2 + n/4+ n/8…$$, cujo limite é 2*n.
Para isso, podemos guardar um set com todos os índices que ainda não foram eliminados, e para cada bit, fazer uma pergunta sobre todos os índices no set, guardar em um outro set com os índices que tem o bit atual ativo. Se o tamanho desse set for menor que $$(tamanno do set global + 1)/2$$, o set global passa a conter somente os elementos do set local, caso contrário são removidos do set global todos os elementos do set local.
Segue o código comentado, para melhor compreensão:
https://gist.github.com/PedroRacchetti/177d91af37ab839b7b2a8cdaaddce8bf