2275. Combinación más grande con bitwise y mayor que cero

dificultad: mediano

temas: array, tabla hash, manipulación de bits, contando

el bitwise y de una matriz nums es el bitwise y de todos los enteros en nums.

• Por ejemplo, para nums = [1, 5, 3], el bitwise y es igual a 1 y 5 y 3 = 1.
• también, para nums = [7], el bitwise e es 7.

se le da una variedad de candidatos de enteros positivos. Evalúe el bitwise y de cada combinación de números de candidatos. Cada número en candidatos solo puede usarse una vez en cada combinación.

return el tamaño de la combinación más grande de candidatos con un bitwise y great que 0 .

Ejemplo 1:

• Entrada: candidates = [16,17,71,62,12,24,14]
• output: 4
• Explicación: La combinación [16,17,62,24] tiene un bitwise y de 16 y 17 y 62 y 24 = 16> 0.
  • El tamaño de la combinación es 4.
  • Se puede demostrar que ninguna combinación con un tamaño mayor que 4 tiene un bitwise y mayor que 0.
  • Tenga en cuenta que más de una combinación puede tener el tamaño más grande.
  • Por ejemplo, la combinación [62,12,24,14] tiene un bitwise y de 62 y 12 & 24 & 14 = 8> 0.

Ejemplo 2:

• input: candidates = [8,8]
• output: 2
• Explicación: La combinación más grande [8,8] tiene un bitwise y de 8 & 8 = 8> 0.
  • El tamaño de la combinación es 2, por lo que regresamos 2.

restricciones:

• 1 5
• 1 7

Pista:

1. para el bit a bit y para ser mayor que cero, al menos un bit debería ser 1 para cada número en la combinación.
2. Los candidatos tienen 24 bits de largo, por lo que para cada posición de bit, podemos calcular el tamaño de la combinación más grande de tal manera que el bit a 1 en esa posición de bits.

Solución:

Necesitamos centrarnos en identificar grupos de números donde al menos una posición de bit en su representación binaria permanece establecida (1) en todos los números en la combinación.

Resumen de la solución

1. bit Analysis : Dado que cada número en los candidatos puede ser representado por un número binario con hasta 24 bits (como 1

2. Conteo de bits en cada posición : para cada posición de bit, cuente cuántos números en los candidatos tienen ese bit establecido en 1. Si múltiples números comparten un poco en la misma posición, podrían formar una combinación con un bit a cero y mayor que cero en esa posición de bit.

3. Encuentre el recuento más grande : el mayor número de números con un bit establecido en cualquier posición dada será la respuesta, ya que representa la combinación más grande posible donde el resultado y el resultado es mayor que cero.

Ejemplo

Considere candidatos = [16, 17, 71, 62, 12, 24, 14]:

• Convierta cada número en binario y analice las posiciones de bits.
• cuente cuántas veces se establece cada bit en todos los números.
• Encuentre el recuento máximo en todas las posiciones de bits.

Implementemos esta solución en php: 2275. Combinación más grande con bitwise y mayor que cero

Explicación:

1. bucle a través de cada posición de bit : iteramos sobre cada posición de bit de 0 a 23.
2. Cuente números con bit set : para cada posición, cuente cuántos números en los candidatos tienen ese conjunto de bits específico.
3. actualizar el tamaño de combinación máxima : rastrear el recuento más alto en todas las posiciones de bits.
4. devuelve el resultado : el resultado es el tamaño de combinación más grande con un bitwise y mayor que cero, según sea necesario.

Análisis de complejidad

• Time Complexity : o (n x 24) = o (n) , donde n es el número de elementos en los candidatos, porque realizamos 24 operaciones (una para cada posición de bit) para cada número
• espacio complejidad : o (1) , ya que solo estamos usando una cantidad fija de espacio adicional.

Este enfoque es lo suficientemente eficiente como para manejar el límite de tamaño de entrada (candidates.length 5 ).

Enlaces de contacto

Si encontró esta serie útil, considere dar el repositorio una estrella en GitHub o compartir la publicación en sus redes sociales favoritas. ¡Tu apoyo significaría mucho para mí!

Si desea un contenido más útil como este, no dude en seguirme:

• linkedin
• github