Uso inteligente do operador XOR para encontrar o número perdido

Question

Encontrei o seguinte problema no leetcode e tentei resolvê-lo com o código a seguir, mas parece haver uma solução ainda melhor que tira proveito do XOR.Leetcode tem uma descrição para a solução XOR, mas não consigo entendê-la na íntegra.

Eu simplesmente não consigo entender por que precisamos inicializar a variável ausente com o comprimento da matriz, por que não inicializá-lo com Zero e quando inicializamos com Zero, por que esse algoritmo não consegue encontrar o número que falta?Alguém pode explicar isso?

A seguir estava minha solução antes de aprender que a solução XOR sugerida pelo Leetcode é ainda melhor e mais rápida

class Solution {
    public int missingNumber(int[] nums) {
        if(nums.length == 1)
            return nums[0] == 0 ? 1 : 0;

        int missing = 0;
        boolean tempNums[] = new boolean[nums.length+1]; //cuz one is missing

        for(int i:nums) {
            tempNums[i] = true;
        }

        for(int i=0; i<tempNums.length; i++)
            if(!tempNums[i]) {
                missing = i;
                break;
            }
        return missing;
    }
}

Answer 1

Vamos usar um exemplo mais simples para verificar o fato.

Suponha $n=1$, ou seja, recebemos um array contendo um número (distinto) retirado de 0, 1.

• Se o número fornecido for 0, então o número que falta deve ser $1=1 erreno0$.
• Se o número fornecido for 1, então o número que falta deve ser $0=1 erreno1$.

Para resumir, se o número fornecido for $a$, então o número que falta é $1 erreno a=n erreno a ot=0 erreno a$.

---

Quais são as razões fundamentais por trás desta magia em situações gerais?

Acontece que o operador XOR bit a bit, comumente denotado por "$ erra$"em linguagens de programação, se comporta como o operador de adição comum.

• Isso é comutativo e associativo.Portanto, a ordem das operações não importa em nada.
• $0$ funciona como um zero, ou seja, $a erra 0=a$.Então $0$podem ser removidos.
• $a erra a = 0$ para cada número $a$.Portanto, se o mesmo número aparecer duas vezes, eles se cancelam.

Fora das linguagens de programação, o XOR bit a bit é mais comumente escrito como "$\oplus$", onde o símbolo de mais, "$+$"no centro nos lembra que ele se comporta como uma adição comum.

Agora considere a expressão, $$(0\oplus1\oplus2\oplus3\cdots\oplus n)\oplus( a_0\oplus a_1\oplus a_2\cdots\oplus a_{n-1}).$$Sempre que houver um par do mesmo número, podemos removê-los.Portanto, todos os números são cancelados entre si, exceto o número que falta, já que esse número que falta é o único número que aparece em $$0\oplus1\oplus2\oplus3\cdots\oplus n$$ mas não em $$a_0\oplus a_1\oplus a_2\cdots\oplus a_{n-1}.$$ Então,

$$(0\oplus1\oplus2\oplus3\cdots\oplus n)\oplus( a_0\oplus a_1\oplus a_2\cdots\oplus a_{n-1})= ext{o número que falta} $$

Vamos mudar a ordem da “soma” no lado esquerdo.Podemos emparelhar $0$ com $a_0$, $1$ com $a_1$, $2$ com $a_2$, $\cdots$, $n-1$ com $a_{n-1}$, deixando apenas $n$ desemparelhado.Vemos que o lado esquerdo é$$(0\oplus a_0)\oplus(1\oplus a_1)\oplus(2\oplus a_2)\oplus\cdots(n-1\oplus a_{n-1})\oplus n.$$Agora, basta se mover $n$ para a frente da expressão.

---

"Eu simplesmente não consigo entender por que precisamos inicializar a variável ausente com o comprimento do array.Por que não inicializá-lo com Zero e quando inicializamos com Zero, por que esse algoritmo não consegue encontrar o número que falta?"

Não há nada de especial em inicializar a variável ausente com $n$, o comprimento da matriz.Você certamente pode inicializá-lo com qualquer número, incluindo zero.Então você deve emparelhar o restante números com $a_0, a_2,\cdots, a_{n-1}$ (arbitrariamente, cada número exatamente uma vez).Por exemplo, temos

$$0\oplus(1\oplus a_0)\oplus(2\oplus a_1)\oplus\cdots(n\oplus a_{n-1})= ext{o número que falta} $$

Na verdade, não precisamos fazer o emparelhamento.Podemos até pré-calcular diretamente $$ f (n) = 0 opLus1 opLus2 opLus3 cdots oplus n = Begin {casos} n & text {if} n = 0 pmod4 1 & text {if} n = 1 pmod4 n+1 & text {if} n = 2 pmod4 0 & text {if} n = 3 pmod4 end {casos} $$e então calcule$$f(n)\oplus a_0\oplus a_1\oplus a_2\cdots\oplus a_{n-1},$$o que também produzirá o número que falta.Portanto, temos o seguinte programa mais rápido para calcular o número que falta.

public int missingNumber(int[] nums) {
    final int length = nums.length;
    // missing = length, 1, length + 1, 0 when length = 0, 1, 2, 3 mod 4.
    int missing = length % 2 == 0 ? length + (length / 2 % 2) : (length + 1) / 2 % 2;
    for (int i : nums) missing ^= i;

    return missing;
}

A abordagem acima é muito semelhante à Abordagem # 4 Fórmula de Gauss no Leetcode.

Answer 2

Comece com uma lista de quaisquer n inteiros.Duplique os inteiros e calcule o XOR se esses 2n inteiros.Qual é o resultado?Reorganize os 2n inteiros de qualquer forma e calcule seu XOR.Qual é o resultado.Remova um número x da lista e calcule o XOR.Qual é o resultado?Remova outro número y e calcule o XOR.Qual é o resultado?

Agora volte ao seu problema, e as respostas que você deu antes lhe dirão imediatamente qual será o seu resultado.