Question
Dado um array contendo todos os números de 1 a n exceto dois, encontre os dois números que faltam.
por exemplo.
ausente ([4, 2, 3]) = 1, 5
Responda
// Determine o único número que está faltando.
// XOR o array real e o array esperado de 1 a N juntos. Todos
// os números repetidos se cancelam, deixando-nos com o resultado desejado.
// (1 ^ 2 ^ … ^ N-1 ^ N) ^ (1 ^ 2 ^ … ^ N-1) = N
público estático int oneMissing (int [] arr) {
int totalXor = 0;
int arrXor = 0;
// XOR the numbers from 1 to N, ie. the input if no numbers were missing
for (int i = 1; i <= arr.length + 1; i++) totalXor ^= i;
// XOR the input array
for (int i : arr) arrXor ^= i;
// XOR the two values together. x^x = 0 and x^0 = x. That means that any
// repeated number cancels out, so we are left with the single
// non-repeated number.
// eg. (1 ^ 2 ^ ... ^ N-1 ^ N) ^ (1 ^ 2 ^ ... ^ N-1) = N
return totalXor ^ arrXor;}
// Determine os dois números que faltam em uma matriz. Retorna uma matriz de
// comprimento 2
public static int [] twoMissing (int [] arr) {
int size = arr.length + 2;
// 1 + 2 + ... + N-1 + N = N * (N + 1) / 2
long totalSum = size * (size + 1) / 2;
// Sum up the input array
long arrSum = 0;
for (int i : arr) arrSum += i;
// totalSum - arrSum = the sum of the two results. Therefore we know
// that since our two results are not equal, one result is
// > (sum of two results) / 2 and the other is
// < (sum of two results) / 2
int pivot = (int) ((totalSum - arrSum) / 2);
// Use the same technique as oneMissing() on each half of the array.
int totalLeftXor = 0;
int arrLeftXor = 0;
int totalRightXor = 0;
int arrRightXor = 0;
for (int i = 1; i <= pivot; i++) totalLeftXor ^= i;
for (int i = pivot + 1; i <= size; i++) totalRightXor ^= i;
for (int i : arr) {
if (i <= pivot) arrLeftXor ^= i;
else arrRightXor ^= i;
}
return new int[]{totalLeftXor ^ arrLeftXor, totalRightXor ^ arrRightXor};}
// Determine o único número que está faltando.
// XOR o array real e o array esperado de 1 a N juntos. Todos
// os números repetidos se cancelam, deixando-nos com o resultado desejado.
// (1 ^ 2 ^ … ^ N-1 ^ N) ^ (1 ^ 2 ^ … ^ N-1) = N
público estático int oneMissing (int [] arr) {
int totalXor = 0;
int arrXor = 0;
// XOR the numbers from 1 to N, ie. the input if no numbers were missing
for (int i = 1; i <= arr.length + 1; i++) totalXor ^= i;
// XOR the input array
for (int i : arr) arrXor ^= i;
// XOR the two values together. x^x = 0 and x^0 = x. That means that any
// repeated number cancels out, so we are left with the single
// non-repeated number.
// eg. (1 ^ 2 ^ ... ^ N-1 ^ N) ^ (1 ^ 2 ^ ... ^ N-1) = N
return totalXor ^ arrXor;}
// Determine os dois números que faltam em uma matriz. Retorna uma matriz de
// comprimento 2
public static int [] twoMissing (int [] arr) {
int size = arr.length + 2;
// 1 + 2 + ... + N-1 + N = N * (N + 1) / 2
long totalSum = size * (size + 1) / 2;
// Sum up the input array
long arrSum = 0;
for (int i : arr) arrSum += i;
// totalSum - arrSum = the sum of the two results. Therefore we know
// that since our two results are not equal, one result is
// > (sum of two results) / 2 and the other is
// < (sum of two results) / 2
int pivot = (int) ((totalSum - arrSum) / 2);
// Use the same technique as oneMissing() on each half of the array.
int totalLeftXor = 0;
int arrLeftXor = 0;
int totalRightXor = 0;
int arrRightXor = 0;
for (int i = 1; i <= pivot; i++) totalLeftXor ^= i;
for (int i = pivot + 1; i <= size; i++) totalRightXor ^= i;
for (int i : arr) {
if (i <= pivot) arrLeftXor ^= i;
else arrRightXor ^= i;
}
return new int[]{totalLeftXor ^ arrLeftXor, totalRightXor ^ arrRightXor};