java - example - Intentar encontrar el número de x que satisface n+x=n ^ x falla con el tiempo de espera

joptionpane java

Question

Estoy tratando de resolver el siguiente problema de la sección Manipulación de bits en el sitio de Hacker Rank utilizando nuevas funciones de Java 8 como Stream s.

La descripción del problema:

Dado un entero, n, encuentra cada x tal que:

• 0 <= x <= n
• n + x = n ^ x

donde ^ denota el operador XOR a nivel de bits. Luego, imprima un número entero que indique el número total de x que satisfacen los criterios anteriores.

Restricciones

• 0 <= n <= 10 ¹⁵

Entrada de muestra: 5

Salida de muestra: 2

Explicación:

Para n = 5 , los valores de x 0 y 2 satisfacen las condiciones:

• 5 + 0 = 5 ^ 0 = 5
• 5 + 2 = 5 ^ 2 = 7

Por lo tanto, imprimimos 2 como nuestra respuesta.

Entrada de muestra: 10

Salida de muestra: 4

Explicación: Para n = 10 , los valores x 0 , 1 , 4 y 5 satisfacen las condiciones:

• 10 + 0 = 10 ^ 0 = 10
• 10 + 1 = 10 ^ 1 = 11
• 10 + 4 = 10 ^ 4 = 14
• 10 + 5 = 10 ^ 5 = 15

Por lo tanto, imprimimos 4 como nuestra respuesta.

Mi código es el siguiente:

public class SumVsXor 
{
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long count = LongStream.rangeClosed(0, n)
                               .filter(k -> k + n == (k ^ n))
                               .count();
        System.out.println(count);  
    }
}

El problema es que este código no pasa todos los casos de prueba.

Funciona para valores pequeños de n , pero para valores grandes como 1000000000000000 falla debido a un tiempo de espera.

Me pregunto si LongStream no puede manejar Stream con tantos elementos.

Answer 1

El problema con tu código es que es muy ineficiente. Para el caso de n==1000000000000000 , su canalización de Stream está realizando 1,000,000,000,000,000 operaciones de suma y XOR, lo que lleva mucho tiempo. Probar para cada número entre 0 y n si n + x == n ^ x tomaría mucho tiempo incluso si usas un bucle for en lugar de Stream s.

En lugar de verificar todos los números entre 0 y n, debe tratar de encontrar una mejor manera de calcular el número total requerido de x. El hecho de que este problema aparezca en la sección "Manipulación de bits" debería darle una pista para ver los bits de números que satisfacen
n + x == n ^ x .

Consideremos el caso de n==1000000000000000 . La representación binaria de ese gran número es

0000000000000011100011010111111010100100110001101000000000000000
              ===   == = ====== = =  =  ==   == =
                 ---  - -      - - -- --  ---  - ---------------
~~~~~~~~~~~~~~              

Para que n + x sea ​​igual a n ^ x , x debe tener un valor de 0 en todos los bits correspondientes a los 1 bits de n (marcado con = arriba), y un valor de 0 o 1 en los bits correspondientes con el 0 bits de n (marcados con - arriba). Esto no incluye los 0 s iniciales (marcados con ~ arriba), ya que x debe ser <= n , por lo que cualquier 0 s en n debe tener un valor 0 en x .

Esto significa que el número total de x para las que n + x == n ^ x es
2 ^{el número de 0 s en n , sin incluir 0 s iniciales} .

En el caso de n = 1000000000000000 , hay 30 bits 0 , por lo que el número total de x que satisfacen el requisito es 2 ³⁰ .

Aquí hay una forma de calcular el número total de x :

long n = 1000000000000000L;
int zeroBitsCount = 0;
while (n > 0) {
    if (n % 2 == 0) {
        zeroBitsCount++; // counts the number of non-leading 0 bits
    }
    n = n >> 1; // divide n by 2 in order to examine the next bit in the next iteration
}
long total = 1L << zeroBitsCount; // the total is 2^(the 0 bits count)

Answer 2

Esta es una pregunta simple si sabes un poco sobre XOR. No sé mucho sobre Java. Pero puedo explicarlo en python.

1. Primero convierte el número a binario. 2.Cuenta el número de ceros en ese número binario. 3.print 2 ^ (número de ceros) y eso es todo.

Aquí está mi código de python.

n = int(input())
sum = 0
if n!=0:
    n=str(bin(n))
    for i in range(len(n)):
            if n[i]==''0'':
           sum = sum + 1
    print(2**(sum-1))
else: print(1)

La razón para disminuir la suma en 1 es que, en Python, convierte el número al binario con este formato. por ejemplo: 0b''10101.

Answer 3

Llegué al mismo resultado, pero a través de una explicación diferente, pensé que podría publicarlo aquí.

La respuesta de Eran llegó a la misma conclusión que yo: modificar los ceros en la representación binaria del número inicial, eso es bastante sencillo.

Supongamos que nuestro número es

101010100

por lo que tiene 5 ceros.

Necesitas todas las combinaciones posibles de:

• un solo cero
• dos ceros
• tres ceros
• cuatro ceros
• cinco ceros

eso es en realidad

 comb(1,5) + comb(2,5) + comb(3,5) + comb(4,5) + comb (5,5)

es una fórmula bien conocida que es igual a:

pow (2, n) // donde n es cinco en nuestro caso

A partir de ahí la solución es obvia ...

Answer 4

public static void main (String[] args) {
    Scanner in = new Scanner (System.in);
    long n = in.nextLong();
    long count = 1L << (64-Long.bitCount(n)-Long.numberOfLeadingZeros(n));
    System.out.println(count);
}