La forma más rápida de encontrar el número faltante en un array de números

No dudes en compartir nuestro espacio y códigos con tus amigos, danos de tu ayuda para hacer crecer nuestra comunidad.

Solución:

Puede hacer esto en O (n). Iterar a través del array y calcular la suma de todos los números. Ahora, la suma de números naturales de 1 a N, se puede expresar como Nx(N+1)/2. En su caso N = 100.

Reste la suma de la array de Nx(N+1)/2, donde N = 100.

Ese es el número que falta. La ranura vacía se puede detectar durante la iteración en la que se calcula la suma.

// will be the sum of the numbers in the array.
int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++)

    if (arr[i] == 0)
    
         idx = i; 
    
    else 
    
         sum += arr[i];
    


// the total sum of numbers between 1 and arr.length.
int total = (arr.length + 1) * arr.length / 2;

System.out.println("missing number is: " + (total - sum) + " at index " + idx);

Podemos usar la operación XOR, que es más segura que la suma, porque en los lenguajes de programación, si la entrada dada es grande, puede desbordarse y dar una respuesta incorrecta.

Antes de ir a la solución, sepa que A xor A = 0. Entonces, si XOR dos números idénticos, el valor es 0.

Ahora, XORing [1..n] con los elementos presentes en el array cancela los números idénticos. Entonces, al final obtendremos el número que falta.

// Assuming that the array contains 99 distinct integers between 1..99
// and empty slot value is zero
int XOR = 0;
for(int i=0; i<100; i++) 
    if (ARRAY[i] != 0) // remove this condition keeping the body if no zero slot
        XOR ^= ARRAY[i];
    XOR ^= (i + 1);

return XOR;
//return XOR ^ ARRAY.length + 1; if your array doesn't have empty zero slot. 

Deja lo dado array ser A con longitud N. Supongamos en el dado array, la única ranura vacía se llena con 0.

Podemos encontrar la solución para este problema utilizando muchos métodos, incluido el algoritmo utilizado en Counting sort. Pero, en términos de uso eficiente del tiempo y el espacio, tenemos dos algoritmos. Uno usa principalmente suma, resta y multiplicación. Otro usa XOR. Matemáticamente, ambos métodos funcionan bien. Pero programáticamente, necesitamos evaluar todos los algoritmos con medidas principales como

• Limitaciones (como los valores de entrada son grandes (A[1...N]) y / o el número de valores de entrada es grande (N))
• Número de verificaciones de condición involucradas
• Número y tipo de operaciones matemáticas involucradas

etc. Esto se debe a las limitaciones de tiempo y / o hardware (limitación de recursos de hardware) y / o software (limitación del sistema operativo, limitación del lenguaje de programación, etc), etc. Vamos a enumerar y valorar los pros y contras de cada uno de ellos. .

Algoritmo 1:

En el algoritmo 1, tenemos 3 implementaciones.

1. Calcule la suma total de todos los números (esto incluye el número desconocido que falta) utilizando la fórmula matemática (1+2+3+...+N=(N(N+1))/2). Aquí, N=100. Calcula la suma total de todos los números dados. Restar el segundo resultado del primer resultado dará el número que falta.

   Missing Number = (N(N+1))/2) - (A[1]+A[2]+...+A[100])

2. Calcule la suma total de todos los números (esto incluye el número desconocido que falta) utilizando la fórmula matemática (1+2+3+...+N=(N(N+1))/2). Aquí, N=100. De ese resultado, restar cada número dado da el número que falta.

   Missing Number = (N(N+1))/2)-A[1]-A[2]-...-A[100]

   (Note:Aunque la fórmula de la segunda implementación se deriva de la primera, desde el punto de vista matemático ambas son iguales. Pero desde el punto de vista de la programación, ambos son diferentes porque la primera fórmula es más propensa al desbordamiento de bits que la segunda (si los números dados son lo suficientemente grandes). Aunque la suma es más rápida que la resta, la segunda implementación reduce la posibilidad de desbordamiento de bits causado por la suma de valores grandes (no se elimina por completo, porque todavía hay una posibilidad muy pequeña desde (N+1) está en la fórmula). Pero ambos son igualmente propensos al desbordamiento de bits por multiplicación. La limitación es que ambas implementaciones dan un resultado correcto solo si N(N+1)<=MAXIMUM_NUMBER_VALUE. Para la primera implementación, la limitación adicional es que da un resultado correcto solo si Sum of all given numbers<=MAXIMUM_NUMBER_VALUE.)

3. Calcule la suma total de todos los números (esto incluye el número desconocido que falta) y reste cada número dado en el mismo ciclo en paralelo. Esto elimina el riesgo de desbordamiento de bits por multiplicación, pero es propenso a desbordamiento de bits por suma y resta.

   //ALGORITHM
missingNumber = 0;
foreach(index from 1 to N)

   missingNumber = missingNumber + index;
//Since, the empty slot is filled with 0,
//this extra condition which is executed for N times is not required.
//But for the sake of understanding of algorithm purpose lets put it.
if (inputArray[index] != 0)
missingNumber = missingNumber - inputArray[index];


En un lenguaje de programación (como C, C ++, Java, etc.), si el número de bits que representan un tipo de datos enteros es limitado, entonces todas las implementaciones anteriores son propensas al desbordamiento de bits debido a la suma, resta y multiplicación, lo que da como resultado un resultado incorrecto. en caso de valores de entrada grandes (A[1...N]) y / o un gran número de valores de entrada (N).

Algoritmo 2:

Podemos usar la propiedad de XOR para obtener una solución para este problema sin preocuparnos por el problema del desbordamiento de bits. Y también XOR es más seguro y más rápido que la suma. Conocemos la propiedad de XOR de que XOR de dos números iguales es igual a 0 (A XOR A = 0). Si calculamos el XOR de todos los números de 1 a N (esto incluye el número desconocido que falta) y luego, con ese resultado, XOR todos los números dados, los números comunes se cancelan (ya que A XOR A=0) y al final obtenemos el número que falta. Si no tenemos un problema de desbordamiento de bits, podemos usar algoritmos de suma y basados ​​en XOR para obtener la solución. Pero, el algoritmo que usa XOR es más seguro y más rápido que el algoritmo que usa suma, resta y multiplicación. Y podemos evitar las preocupaciones adicionales causadas por la suma, resta y multiplicación.

En todas las implementaciones del algoritmo 1, podemos usar XOR en lugar de sumas y restas.

Asumamos, XOR(1...N) = XOR of all numbers from 1 to N

Implementación 1 => Missing Number = XOR(1...N) XOR (A[1] XOR A[2] XOR...XOR A[100])

Implementación 2 => Missing Number = XOR(1...N) XOR A[1] XOR A[2] XOR...XOR A[100]

Implementación 3 =>

//ALGORITHM
missingNumber = 0;
foreach(index from 1 to N)

    missingNumber = missingNumber XOR index;
    //Since, the empty slot is filled with 0,
    //this extra condition which is executed for N times is not required.
    //But for the sake of understanding of algorithm purpose lets put it.
    if (inputArray[index] != 0)
        missingNumber = missingNumber XOR inputArray[index];

Las tres implementaciones del algoritmo 2 funcionarán bien (también desde el punto de vista programático). Una optimización es similar a

1+2+....+N = (N(N+1))/2

Tenemos,

1 XOR 2 XOR .... XOR N = N if REMAINDER(N/4)=0, 1 if REMAINDER(N/4)=1, N+1 if REMAINDER(N/4)=2, 0 if REMAINDER(N/4)=3

Podemos probar esto por inducción matemática. Entonces, en lugar de calcular el valor de XOR (1 ... N) por XOR todos los números de 1 a N, podemos usar esta fórmula para reducir el número de operaciones XOR.

Además, el cálculo de XOR (1 ... N) utilizando la fórmula anterior tiene dos implementaciones. Implementación sabia, calculando

// Thanks to https://a3nm.net/blog/xor.html for this implementation
xor = (n>>1)&1 ^ (((n&1)>0)?1:n)

es más rápido que calcular

xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;

Entonces, el código Java optimizado es,

long n = 100;
long a[] = new long[n];

//XOR of all numbers from 1 to n
// n%4 == 0 ---> n
// n%4 == 1 ---> 1
// n%4 == 2 ---> n + 1
// n%4 == 3 ---> 0

//Slower way of implementing the formula
// long xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;
//Faster way of implementing the formula
// long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);
long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);

for (long i = 0; i < n; i++)

    xor = xor ^ a[i];

//Missing number
System.out.println(xor);

Tienes la opción de añadir valor a nuestro contenido informacional participando con tu veteranía en las observaciones.

---

---

Utiliza Nuestro Buscador