En primer lugar, debemos entender que no podemos enumerar todos los subconjuntos y encontrar la respuesta. Si hiciéramos eso, la solución tendría una complejidad de [matemáticas] T * (2 ^ N) [/ matemáticas]. con N hasta [matemáticas] 10 ^ 5 [/ matemáticas], simplemente no podemos hacerlo.
Entonces tendremos que encontrar una solución más óptima.
Si pasa algún tiempo con la pregunta, puede observar lo siguiente:
Considere N = 3 y A = 5, B = 6, C = 7;
Sabemos,
5 = 1 0 1
6 = 1 1 0
7 = 1 1 1
Al encontrar el XORSum de manera convencional, terminamos con 28. Pero bueno, tenemos un patrón allí. En las representaciones binarias de los números anteriores, considere la columna más a la izquierda. Tenemos dos 1 y un 0.
Suponga que encuentra el XORSum de estos tres números, terminará con 4. Los subconjuntos que obtendrá serán (1), (0), (1), (1, 0), (0, 1) , (1,1) y (1, 0, 1). Intente comprender aquí que cada uno de los 1 pudo incrementar el XORSum en uno exactamente dos veces. Primero cuando apareció en el subconjunto singleton y la segunda vez cuando apareció solo 0 como subconjunto. Tenemos el mismo número de 1 y 0 en la segunda columna para. El XORSum de la segunda columna también será 4. Pero el número de 1 y 0 es diferente en la columna de la derecha es diferente. Tenemos tres 1’s por allí. ¿Cómo hacemos para encontrar el XORSum de esta columna?
Bueno, los subconjuntos son (1), (1), (1), (1, 1), (1, 1), (1, 1) y (1, 1, 1). Terminamos con el mismo XORSum de 4.
Ahora sumamos los XORSum y Voila individuales .. !! Terminamos con 28. (No hay puntos para adivinar. Era obvio).
Lo más importante que podemos sacar de aquí es que si conocemos la configuración de cada una de las columnas y la suma que equivaldrá de antemano, realmente no necesitamos encontrar los subconjuntos. Tendremos una solución lineal.
¿Cómo utilizamos ésta información?
O podemos precalcular todos los XORSum de todas las configuraciones posibles o podemos hacer algo más interesante, encontrar otro patrón.
Ahora lo más hermoso que descubrimos es lo siguiente. El XORSum de cualquier columna no depende en absoluto del número de 1 y 0.
Sin embargo, depende del número de elementos en la columna. Las relaciones son las siguientes:
¡Si tienes incluso un solo 1, el XORSum de una columna que tiene x elementos será igual a 2 elevado a la potencia (x – 1) … !!
- ¿Cómo funciona el algoritmo OKCupid?
- ¿Cómo funciona la detección de vandalismo de Wikipedia?
- ¿Cómo escribo un algoritmo para el problema de las 100 puertas?
- Cómo hacer que un algoritmo se visualice como visualgo.net
- ¿Qué tipo de algoritmos usa Android para mezclar tu música?
Entonces la lógica debe ser clara. Debe extraer cada columna de dígitos binarios del número, si la columna tiene incluso un solo 1, sume 2 elevado a (N-1) multiplicado por la potencia correspondiente de 2 (para convertir de binario a decimal) al XORSum y eso debería darte la respuesta final.
Yo mismo no he codificado la solución, por lo que podría haber un par de puntos que me he perdido, en caso de que encuentre alguno de ellos o su solución falle por algún motivo, comente a continuación. Feliz codificación 🙂
