Counting Bits

Q: Quelle est la complexité temporelle de Counting Bits ?

La meilleure solution s’exécute en O(n) : chacune des n+1 entrées provient d’une entrée précédente à laquelle on ajoute une unité. Compter séparément les bits de chaque nombre prend O(n log n). Les deux utilisent O(1) mémoire en plus du tableau de sortie.

Q: Existe-t-il une autre récurrence en O(n) pour le comptage des bits ?

Oui. i & (i-1) efface le bit 1 de poids le plus faible de i , donc bits[i] = bits[i & (i-1)] + 1 pour tout i supérieur ou égal à 1. Pour 12 ( 1100 ), 12 & 11 vaut 8 ( 1000 ), qui contient un seul 1, donc 12 en contient deux.

Q: Est-ce que je peux utiliser une fonction popcount intégrée ?

En appeler un pour chaque nombre, comme Integer.bitCount en Java ou __builtin_popcount en C et C++, donne une réponse correcte. Les recruteurs demandent généralement la version sans cela, car l’objectif du problème est de réutiliser les réponses que vous avez déjà calculées.

FacileManipulation de bits Programmation dynamique

+10

Étant donné un entier n supérieur ou égal à 0, renvoie un tableau de n+1 entrées où l’entrée i correspond au nombre de 1 dans la représentation binaire de i, pour chaque i de 0 à n.

Fonction

countBits(n: integer) → integer-array

ninteger: le dernier nombre à compter, 0 ou plus
Renvoieinteger-array: un tableau de n+1 comptes, où l’entrée i est le nombre de bits à 1 dans i

Contraintes

0 ≤ n ≤ 2 × 10⁴

Exemples

Entrée: n = 2
Sortie: [0, 1, 1]
Explication: En binaire, 0 est 0, 1 est 1 et 2 est 10 : aucun 1, puis un, puis un.

Entrée: n = 5
Sortie: [0, 1, 1, 2, 1, 2]
Explication: 3 est 11 et 5 est 101, deux 1 chacun ; 4 est 100, avec un seul. Avec 0, 1 et 2 du premier exemple, les nombres sont 0, 1, 1, 2, 1, 2.

Pour aller plus loin

Peux-tu remplir tout le tableau en O(n) temps, sans fonction intégrée qui compte les bits et sans compter chaque nombre depuis zéro ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Compter chaque nombre depuis le début répète le travail : 13 est 1101, les bits de 6 (110) avec un chiffre supplémentaire à la fin. Remplis les réponses dans l’ordre croissant et chaque entrée réutilise une entrée plus petite avec une addition.

Comptez les bits de chaque nombre

Intuition

Comptez directement les bits à 1 de chaque nombre : ajoutez x & 1 à un compteur, décalez x d’un bit vers la droite, et arrêtez-vous à 0. Pour 13 (1101), les bits obtenus sont 1, 0, 1, 1, donc le compte est 3.

Un nombre inférieur ou égal à n possède environ log2 n chiffres binaires, donc l’exécution est en O(n log n) : environ 20 000 × 15 = 300 000 étapes pour n = 2 × 10^4.

Algorithme

Commencez par une liste de résultats vide.
Pour chaque i de 0 à n, définissez count sur 0 et x sur i.
Tant que x est supérieur à 0, ajoutez x & 1 à count et décalez x vers la droite d’un bit.
Ajoutez count au résultat.
Retournez le résultat.

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

Construire sur la moitié du nombre

Intuition

Décaler i vers la droite d’un rang supprime son dernier chiffre binaire, et i & 1 est ce chiffre. Ainsi, i contient les bits à 1 de i >> 1, auxquels s’ajoute son dernier chiffre : bits[i] = bits[i >> 1] + (i & 1).

Pour tout i supérieur ou égal à 1, i >> 1 est inférieur à i. Remplir le tableau de gauche à droite, en commençant par bits[0] = 0, signifie donc que la valeur lue est toujours déjà disponible. Pour n = 5 : bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2.

Chaque entrée nécessite un décalage, un ET binaire et une addition : temps O(n) et aucune mémoire supplémentaire en dehors du résultat.

Algorithme

Créez un tableau bits de n+1 zéros. bits[0] reste à 0.
Pour i de 1 à n, définissez bits[i] à bits[i >> 1] + (i & 1).
Retournez 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

Pièges et cas limites

Renvoyer n entrées au lieu de n+1. Pour n = 0, la réponse est [0].
Priorité des opérateurs. En Python, C, Java et JavaScript, + est prioritaire sur &, donc bits[i >> 1] + i & 1 signifie (bits[i >> 1] + i) & 1. Conservez les parenthèses autour de (i & 1).
Récupérer bits[i-1] au lieu de bits[i >> 1]. Les nombres voisins ne suivent aucune règle simple : 7 est 111 avec trois 1, et 8 est 1000 avec un seul.
En Lua et R, les tableaux commencent à 1, donc le compte pour i se trouve à l’indice i+1 et la récupération de i >> 1 à floor(i/2) + 1. Lua 5.1 ne possède pas d’opérateur de décalage, donc divisez par deux avec math.floor(i / 2).

Questions fréquentes3

Quelle est la complexité temporelle de Counting Bits ?

La meilleure solution s’exécute en O(n) : chacune des n+1 entrées provient d’une entrée précédente à laquelle on ajoute une unité. Compter séparément les bits de chaque nombre prend O(n log n). Les deux utilisent O(1) mémoire en plus du tableau de sortie.

Existe-t-il une autre récurrence en O(n) pour le comptage des bits ?

Oui. i & (i-1) efface le bit 1 de poids le plus faible de i, donc bits[i] = bits[i & (i-1)] + 1 pour tout i supérieur ou égal à 1. Pour 12 (1100), 12 & 11 vaut 8 (1000), qui contient un seul 1, donc 12 en contient deux.

Est-ce que je peux utiliser une fonction popcount intégrée ?

En appeler un pour chaque nombre, comme Integer.bitCount en Java ou __builtin_popcount en C et C++, donne une réponse correcte. Les recruteurs demandent généralement la version sans cela, car l’objectif du problème est de réutiliser les réponses que vous avez déjà calculées.

def countBits(n):
    # Écrivez le code ici

Test #1

Test #2

Argument

n = 2

Résultat attendu

[0, 1, 1]