2275. Maior combinação com bit e maior que zero

dificuldade: Medium

tópicos: Array, tabela de hash, manipulação de bit, contando

o bitwise e de uma matriz nums é o bit e de todos os números inteiros em nums.

• por exemplo, para nums = [1, 5, 3], o bit -sise e é igual a 1 & 5 & 3 = 1.
• Além disso, para nums = [7], o bit e é 7.

você recebe uma variedade de números inteiros positivos. Avalie o bitwise e de cada combinação de números de candidatos. Cada número em candidatos só pode ser usado uma vez em cada combinação.

retorna o tamanho da combinação maior de candidatos com um bit e maior do que 0 .

Exemplo 1:

• Input: candidatos = [16,17,71,62,12,24,14]
• output: 4
• Explicação: A combinação [16,17,62,24] tem um pouco de bit e de 16 e 17 e 62 e 24 = 16> 0.
  • O tamanho da combinação é 4.
  • pode ser mostrado que nenhuma combinação com um tamanho maior que 4 tem um bit e maior que 0.
  • Observe que mais de uma combinação pode ter o maior tamanho.
  • Por exemplo, a combinação [62,12,24,14] tem um bit e de 62 e 12 e 24 e 14 = 8> 0.

Exemplo 2:

• entrada: candidates = [8,8]
• output: 2
• Explicação: A maior combinação [8,8] tem um bit e de 8 & 8 = 8> 0.
  • O tamanho da combinação é 2, então retornamos 2.

restrições:

• 1 5
• 1 7

Dica:

1. para o bit e para ser maior que zero, pelo menos um bit deve ser 1 para cada número na combinação.
2. Os candidatos têm 24 bits de comprimento; portanto, para cada posição, podemos calcular o tamanho da maior combinação de tal forma que o bit e terá um 1 nessa posição de bit.

Solução:

precisamos nos concentrar na identificação de grupos de números, onde pelo menos uma posição de bit em sua representação binária permanece definida (1) em todos os números na combinação.

Esboço da solução

1. BIT ANASIAL : Como cada número nos candidatos pode ser representado por um número binário com até 24 bits (como 1

,

2. Count Set Bits em cada posição : Para cada posição de bit, conte quantos números nos candidatos tiveram esse bit definido como 1.

3. Encontre a maior contagem

   : o maior número de números com um bit definido em qualquer posição será a resposta, pois representa a maior combinação possível em que o resultado bit e é maior que zero.

Exemplo

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

• conte quantas vezes cada bit é definido em todos os números.
• encontre a contagem máxima em todas as posições de bits.
Vamos implementar esta solução em PHP:

Php /** * @param inteiro [] $ candidatos * @return inteiro */ Função Maiorcombination ($ candidatos) { ... ... ... /** * vá para ./solution.php */ } // Exemplo de uso $ candidatos = [16, 17, 71, 62, 12, 24, 14]; eco maior combinação ($ candidatos); // Saída: 4 ?>

Faça um loop através de cada posição de bit
1. : iteramos sobre cada posição de bit de 0 a 23. !
2. Atualize tamanho máximo de combinação : rastrear a contagem mais alta em todas as posições de bits.
3. retorna o resultado : o resultado é o maior tamanho de combinação com um bit e maior que zero, conforme necessário.
4. Análise de complexidade

:

o (n x 24) = o (n)
• , where n é o número de elementos em candidatos, porque executamos 24 operações (um para a posição de bit) para a posição de cada bit) para cada número. complexidade espacial : o (1)
• , já que estamos usando apenas uma quantidade fixa de espaço extra. Esta abordagem é eficiente o suficiente para lidar com o limite de tamanho de entrada (candidatos.length 5 ).

Se você achou essa série útil, considere dar o

uma estrela no github ou compartilhar a postagem em suas redes sociais favoritas?. Seu apoio significaria muito para mim! Se você quiser um conteúdo mais útil como este, fique à vontade para me seguir:

Linkedin

github