pregunta algoritmo Tricky

Question

Duplicar posibles:
Quickest way to find missing number in an array of numbers

de entrada: array sin clasificar A [1, .., n], que contiene todos menos uno de los números enteros en el rango de 0, .., n

El problema es determinar el entero faltante en el tiempo O (n). Cada elemento de A es representado en binario, y la única operación disponible es el bit de función (i, j), que devuelve el valor del j-ésimo bit de A [i] y toma un tiempo constante.

¿Alguna idea? Creo que algún tipo de algoritmo de dividir y vencer sería apropiado, pero no puedo pensar qué debería hacer exactamente. ¡Gracias por adelantado!

Answer 1

Es una propiedad matemática de que la suma de los números entre 1 y n donde n es n(n+1)/2. Esto se puede ver por 10:

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 
= (1+10) + (2+9) + (3+8) +(4+7) + (5+6) 
= 11 + 11 + 11 + 11 + 11 
= 55 

Así, por extensión, es la suma de los números 0-n ya que apenas está añadiendo 0 a él. Entonces, lo que debes hacer es sumar todos los números y mantener un conteo, luego usa esa fórmula para descubrir el que falta.

Por lo tanto, algo así como:

count = 0 
sum = 0 
foreach num in list: 
    sum = sum + num 
    count = count + 1 
missing = count * (count+1)/2 - sum 

Conseguir el número con bit(i,j) es complicado por lo que tendrá que extraer los bits de forma individual y convertirlas en números reales para sumar.

Answer 2

Es una pregunta trampa, ya que usar el método de bit solo requeriría que ciclo cada bit para cada número, lo que significa que automáticamente se convertiría en O (n * j) donde j es el número de bits que representa n.

Creo que paxdiablo lo tiene, suponiendo que se te permite una solución que no utiliza el método de bits.

Answer 3

Puede utilizar el operador XOR porque es más rápido que la suma. Como tienes acceso a cada bit, estarás haciendo un XOR bit a bit aquí. El principio para ser utilizado aquí es (A XOR B XOR A) = B

por ejemplo: (1 XOR 2 XOR 3) XOR (1 XOR 2) = 3

for i=0 to n 
{ 
Total=Total XOR i 
} 

foreach element in A 
{ 
Total=Total XOR element 
}