Dada una secuencia de números naturales, puede agregar cualquier número natural a cualquier número en la secuencia de modo que su xor se convierta en cero. Mi objetivo es minimizar la suma de los números agregados.
Considere los siguientes ejemplos:
por la respuesta es ; agregando a obtenemos .
Para la respuesta es ; sumando a y a obtenemos .
Para la respuesta es , ya que .
Intenté trabajar en representaciones binarias del número de secuencia, pero se volvió tan complejo. Quiero saber si hay alguna manera simple y eficiente de resolver este problema.
algorithms
integers
xor
Pravin Gadakh
fuente
fuente
Respuestas:
Me parece quea=ai⊕⋯⊕an contiene toda la información necesaria: el 1 bits en a son los bits que necesita para voltear (exactamente) uno de los ai . Como solo puedes agregar , tienes que encontrar unoai donde el bit correspondiente j es 0 y voltearlo: esto causa el mismo costo para todos ai , es decir 2j , entonces la elección no importa. El problema comienza si no existeai .
Es por eso que debe hacer esto de forma iterativa y trabajar desde el bit menos significativo hacia arriba. Proceda como arriba; si no hay adecuadoai , elegir la ai con el número máximo de 1 bits a la izquierda de la posición actual (esto aumenta la posibilidad de encontrar un candidato adecuado en futuras iteraciones), voltee el bit y continúe, es decir, voltee todos a la izquierda hasta que cambie un cero a uno. Tenga en cuenta que todavía agregamos2j ) Como carry se propaga solo a la izquierda, las elecciones anteriores no se invalidan. Recalculara y continuar con j+1 ; iterar hasta que tengaa=0 .
Tenga en cuenta que esto es solo una heurística por lo que puedo decir: la elección dei puede ser subóptimo si causa muchos bits en a para volverse distinto de cero. No estoy seguro de si esto se puede evitar.
fuente
En realidad no tengo una solución, pero aquí hay algunas ideas que surgieron.
Si observa los resultados de XORing todos los números en la secuencia, eso le da un límite superior en el número de adiciones que necesita hacer. Por ejemplo, en su ejemplo de10,4,5,1 , tenemos 10⊕4⊕5⊕1=10 para que sepa que no tiene que agregar más de 8 (porque el conjunto de 8 bits es el más alto). Distribuir hasta ocho "unos" distribuidos de cuatro maneras es un conjunto bastante pequeño de combinaciones. No puedo recordar esa fórmula tan tarde en la noche, pero hay unn! ahí en alguna parte.
Para dar a esa afirmación un poco más de fundamento, considere enteros arbitrariosA,B tal que A⊕B=8 . Los bits superiores al bit 3 obviamente se cancelan, por lo que puede ignorarlos. Para los cuatro bits inferiores, son XOR a 8, por lo que el peor caso posible (en términos de la cantidad de unidades que necesita agregar) es si A=8 y B=0 (todos los ceros excepto el bit más alto) porque necesitará agregar +8 a B para obtener ese conjunto de bits superior. Si hay cualquiera de los bits establecidos en cualquiera de los números, debe agregar menos.
Tal vez pueda comenzar con esto y desarrollar una cantidad máxima más estrecha para agregar.
fuente