Counting Bits

Q: Qual é a complexidade de tempo de Counting Bits?

A melhor solução é executada em tempo O(n): cada uma das n+1 entradas vem de uma entrada anterior com uma adição. Contar os bits de cada número, um de cada vez, leva O(n log n), porque um número até n tem cerca de log2 n dígitos binários. Ambas usam O(1) de memória além do array de saída.

Q: Por que bits[i] = bits[i >> 1] + (i & 1) funciona?

i >> 1 é i com seu último dígito binário removido, e i & 1 é esse dígito removido. Os 1s de i são os 1s do número mais curto mais o último dígito. Para 11, que é 1011 , o número mais curto é 5 ( 101 , dois 1s) e o último dígito é 1, então 11 tem três.

Q: Existe outra recorrência O(n) para contar bits?

Sim. i & (i-1) limpa o bit 1 menos significativo de i , então bits[i] = bits[i & (i-1)] + 1 para todo i maior ou igual a 1. Para 12 ( 1100 ), 12 & 11 é 8 ( 1000 ), que tem um bit 1, então 12 tem dois. É tão rápido quanto a regra de deslocamento e usa o mesmo preenchimento da esquerda para a direita.

Q: Posso usar uma função popcount integrada?

A maioria das linguagens tem uma, como Integer.bitCount em Java ou __builtin_popcount em C e C++, e chamá-la para cada número fornece a resposta correta. Geralmente, os entrevistadores pedem a versão sem ela, porque o objetivo do problema é reutilizar respostas que você já calculou. A recorrência também funciona em linguagens sem uma função desse tipo.

FácilManipulação de bits Programação dinâmica

+10

Você recebe um número inteiro n que é 0 ou maior. Para cada número i de 0 a n, conte quantos 1s aparecem quando i é escrito em binário. Retorne as contagens como um array com n+1 entradas, em que a entrada i é a contagem para o número i.

Função

countBits(n: integer) → integer-array

ninteger: o último número a contar, 0 ou mais
Retornainteger-array: um array de n+1 contagens, em que a entrada i é o número de bits 1 em i

Restrições

0 ≤ n ≤ 2 × 10⁴

Exemplos

Entrada: n = 2
Saída: [0, 1, 1]
Explicação: No sistema binário, 0 é 0, 1 é 1 e 2 é 10. Isso significa nenhum 1, depois um, depois um.

Entrada: n = 5
Saída: [0, 1, 1, 2, 1, 2]
Explicação: 3 é 11 e 5 é 101, dois algarismos 1 cada, enquanto 4 é 100 com um único 1. Com 0, 1 e 2 do primeiro exemplo, as contagens de 0 a 5 são 0, 1, 1, 2, 1, 2.

+15 testes ocultos ao enviar

Para ir além

Você consegue preencher todo o array em tempo O(n), sem uma função integrada que conte bits e sem contar cada número do zero?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Contar os 1s de cada número individualmente funciona, mas repete trabalho. 13 é 1101 e 6 é 110: os bits de 13 são os bits de 6 com mais um dígito no final. Se você preencher as respostas em ordem crescente, a contagem de que precisa para i já está no array, e cada entrada custa uma adição.

Conte os bits de cada número

Intuição

Pegue cada número de 0 até n e conte diretamente seus bits 1. O bit menos significativo de x é x & 1. Some-o a um contador e, em seguida, desloque x para a direita com x >> 1, para que o próximo bit se torne o menos significativo. Pare quando x chegar a 0.

Para 13, que é 1101, os bits são 1, 0, 1, 1 da direita para a esquerda, então a contagem é 3. Cada número exige uma etapa por dígito binário, e um número até n tem cerca de log2 n dígitos.

Isso torna a execução completa O(n log n). Para n = 2 × 10^4, são cerca de 20.000 × 15 = 300.000 etapas, o que é rápido o suficiente. Ainda há trabalho desperdiçado: contar 13 repete cada etapa que você já executou para 6. O espaço é O(1), além do array de saída.

Algoritmo

Inicie uma lista de resultados vazia.
Para cada i de 0 a n, defina count como 0 e x como i.
Enquanto x for maior que 0, adicione x & 1 a count e desloque x para a direita em uma posição.
Adicione count ao resultado.
Retorne o resultado.

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

Construa sobre metade do número

Intuição

Deslocar i uma posição para a direita remove seu último dígito binário. Portanto, i tem exatamente os bits 1 de i >> 1, mais um quando seu último dígito é 1. Esse último dígito é i & 1, o que resulta na regra bits[i] = bits[i >> 1] + (i & 1).

Para todo i maior ou igual a 1, i >> 1 é menor que i. Se você preencher o array da esquerda para a direita, começando com bits[0] = 0, a entrada consultada já estará sempre preenchida. Isso é programação dinâmica: cada resposta é construída a partir de uma menor.

Para n = 5: bits[1] = bits[0] + 1 = 1, bits[2] = bits[1] + 0 = 1, bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2. Cada entrada exige um deslocamento, um AND e uma adição, então o tempo é O(n) e nenhuma memória além da saída é necessária.

Algoritmo

Crie um array bits de n+1 zeros. bits[0] permanece 0.
Para i de 1 até n, defina bits[i] como bits[i >> 1] + (i & 1).
Retorne bits.

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

Armadilhas e casos extremos

A regra cabe em uma linha, então os bugs se escondem ao redor dela.

O array tem n+1 entradas, não n. Para n = 0, a resposta é [0]: uma entrada, para o número 0.
Precedência de operadores. Em Python, C, Java e JavaScript, + tem precedência maior que &, então bits[i >> 1] + i & 1 é interpretado como (bits[i >> 1] + i) & 1. Mantenha os parênteses em torno de (i & 1).
Consultar bits[i-1] em vez de bits[i >> 1]. Números vizinhos não seguem uma regra simples em comum: 7 é 111, com três 1s, e 8 é 1000, com um.
Em Lua e R, os arrays começam em 1, então a contagem para i fica no índice i+1, e a consulta de i >> 1 fica no índice floor(i/2) + 1. O Lua do executor não tem operador de deslocamento, então divida por dois usando math.floor(i / 2).
Transformar cada número em uma string binária e contar os caracteres 1 dá a resposta correta, mas cria uma nova string para cada número.

Perguntas frequentes4

Qual é a complexidade de tempo de Counting Bits?

A melhor solução é executada em tempo O(n): cada uma das n+1 entradas vem de uma entrada anterior com uma adição. Contar os bits de cada número, um de cada vez, leva O(n log n), porque um número até n tem cerca de log2 n dígitos binários. Ambas usam O(1) de memória além do array de saída.

Por que <code>bits[i] = bits[i >> 1] + (i & 1)</code> funciona?

i >> 1 é i com seu último dígito binário removido, e i & 1 é esse dígito removido. Os 1s de i são os 1s do número mais curto mais o último dígito. Para 11, que é 1011, o número mais curto é 5 (101, dois 1s) e o último dígito é 1, então 11 tem três.

Existe outra recorrência O(n) para contar bits?

Sim. i & (i-1) limpa o bit 1 menos significativo de i, então bits[i] = bits[i & (i-1)] + 1 para todo i maior ou igual a 1. Para 12 (1100), 12 & 11 é 8 (1000), que tem um bit 1, então 12 tem dois. É tão rápido quanto a regra de deslocamento e usa o mesmo preenchimento da esquerda para a direita.

Posso usar uma função popcount integrada?

A maioria das linguagens tem uma, como Integer.bitCount em Java ou __builtin_popcount em C e C++, e chamá-la para cada número fornece a resposta correta. Geralmente, os entrevistadores pedem a versão sem ela, porque o objetivo do problema é reutilizar respostas que você já calculou. A recorrência também funciona em linguagens sem uma função desse tipo.

Python

def countBits(n):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

n = 2

Esperado

[0, 1, 1]