Counting Bits
Vous recevez un nombre entier n supérieur ou égal à 0. Pour chaque nombre i de 0 à n, comptez le nombre de 1 présents dans l’écriture binaire de i. Renvoyez les comptes sous forme d’un tableau de n+1 éléments, où l’élément i est le compte pour le nombre i.
Fonction
- ninteger
- le dernier nombre à compter, 0 ou plus
- Renvoieinteger-array
- un tableau de n+1 nombres, où l’entrée i correspond au nombre de bits à 1 dans i
Contraintes
0 ≤ n ≤ 2 × 104
Exemples
- Entrée
- n = 2
- Sortie
- [0, 1, 1]
- Explication
- En binaire, 0 est
0, 1 est1et 2 est10. Cela correspond à aucun 1, puis un, puis un.
- Entrée
- n = 5
- Sortie
- [0, 1, 1, 2, 1, 2]
- Explication
- 3 est
11et 5 est101, chacun avec deux 1, tandis que 4 est100avec un seul 1. Avec 0, 1 et 2 du premier exemple, les nombres de 1 pour les valeurs de 0 à 5 sont 0, 1, 1, 2, 1, 2.
+15 tests cachés à la soumission
Pour aller plus loin
Peux-tu remplir tout le tableau en O(n), sans utiliser de fonction intégrée qui compte les bits et sans recompter chaque nombre depuis zéro ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Écrivez les nombres de 0 à 8 en binaire et comparez un nombre avec celui que vous obtenez en supprimant son dernier chiffre. 6 s’écrit
110et 3 s’écrit11. Comment leurs nombres de 1 se comparent-ils ?Décaler vers la droite d’un bit,
i >> 1, supprime le dernier chiffre binaire dei. Le nombre pouriest le nombre pouri >> 1plus ce dernier chiffre, qui esti & 1.Remplissez un tableau en partant de 0. Lorsque vous atteignez
i, l’entrée pouri >> 1est déjà remplie, car cette valeur est plus petite. Chaque entrée nécessite donc une consultation et une addition.
Solution
Compter les 1 de chaque nombre individuellement fonctionne, mais cela répète du travail. 13 s’écrit 1101 et 6 s’écrit 110 : les bits de 13 sont ceux de 6 avec un chiffre supplémentaire à la fin. Si tu remplis les réponses dans l’ordre croissant, le compte dont tu as besoin pour i se trouve déjà dans le tableau, et chaque entrée ne coûte qu’une addition.
Comptez les bits de chaque nombre
Intuition
Parcourez chaque nombre de 0 à n et comptez directement ses bits à 1. Le bit de poids faible de x est x & 1. Ajoutez-le à un compteur, puis décalez x vers la droite avec x >> 1 pour que le bit suivant devienne le bit de poids faible. Arrêtez-vous lorsque x atteint 0.
Pour 13, qui s’écrit 1101, les bits apparaissent de droite à gauche : 1, 0, 1, 1 ; le compte est donc 3. Chaque nombre coûte une étape par chiffre binaire, et un nombre inférieur ou égal à n comporte environ log2 n chiffres.
La durée totale d’exécution est donc O(n log n). Pour n = 2 × 10^4, cela représente environ 20 000 × 15 = 300 000 étapes, ce qui s’exécute en un temps raisonnable. Cette méthode gaspille tout de même du travail : compter 13 répète chaque étape déjà effectuée pour 6. L’espace utilisé est O(1), hormis le tableau de sortie.
Algorithme
- Commencez une liste de résultats vide.
- Pour chaque
ide 0 àn, définissezcountsur 0 etxsuri. - Tant que
xest supérieur à 0, ajoutezx & 1àcountet décalezxvers la droite d’un bit. - Ajoutez
countau résultat. - Renvoyez 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 bitsConstruire sur la moitié du nombre
Intuition
Décaler i vers la droite d’une position supprime son dernier chiffre binaire. Ainsi, i contient exactement les bits à 1 de i >> 1, plus un de plus lorsque son dernier chiffre vaut 1. Ce dernier chiffre est i & 1, ce qui donne la règle bits[i] = bits[i >> 1] + (i & 1).
Pour tout i supérieur ou égal à 1, i >> 1 est inférieur à i. Si tu remplis le tableau de gauche à droite, en commençant par bits[0] = 0, l’entrée que tu consultes est toujours déjà remplie. C’est de la programmation dynamique : chaque réponse est construite à partir d’une réponse plus petite.
Pour 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. Chaque entrée nécessite un décalage, un AND et une addition ; le temps d’exécution est donc en O(n), et aucune mémoire supplémentaire n’est nécessaire en dehors de celle de la sortie.
Algorithme
- Crée un tableau
bitsden+1zéros.bits[0]reste égal à 0. - Pour
iallant de 1 àn, définisbits[i]commebits[i >> 1] + (i & 1). - Renvoie
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
La règle tient sur une seule ligne, les bogues se cachent donc autour d’elle.
- Le tableau contient
n+1entrées, et nonn. Pourn= 0, la réponse est[0]: une entrée, pour le nombre 0. - Priorité des opérateurs. En Python, C, Java et JavaScript,
+est prioritaire sur&, doncbits[i >> 1] + i & 1se lit comme(bits[i >> 1] + i) & 1. Garde les parenthèses autour de(i & 1). - Consulter
bits[i-1]au lieu debits[i >> 1]. Les nombres voisins ne suivent aucune règle simple : 7 est111avec trois 1, et 8 est1000avec un seul. - En Lua et en R, les tableaux commencent à l’indice 1 : le compte pour
ise trouve donc à l’indicei+1, et la consultation pouri >> 1se fait à l’indicefloor(i/2) + 1. Le Lua du runner ne possède pas d’opérateur de décalage, alors divise par deux avecmath.floor(i / 2). - Convertir chaque nombre en chaîne binaire et compter les caractères
1donne la bonne réponse, mais crée une nouvelle chaîne pour chaque nombre.
Questions fréquentes4
Quelle est la complexité temporelle du comptage des bits ?
La meilleure solution s’exécute en temps O(n) : chacune des n+1 entrées provient d’une entrée précédente à laquelle on ajoute une valeur. Compter les bits de chaque nombre un par un prend O(n log n), car un nombre inférieur ou égal à n comporte environ log2 n chiffres binaires. Les deux solutions utilisent O(1) mémoire en plus du tableau de sortie.
Pourquoi bits[i] = bits[i >> 1] + (i & 1) fonctionne-t-il ?
i >> 1 correspond à i privé de son dernier chiffre binaire, et i & 1 correspond à ce chiffre supprimé. Les 1 de i sont les 1 du nombre plus court auxquels s’ajoute le dernier chiffre. Pour 11, qui s’écrit 1011, le nombre plus court est 5 (101, deux 1) et le dernier chiffre est 1, donc 11 en compte trois.
Existe-t-il une autre récurrence en O(n) pour compter les bits ?
Oui. i & (i-1) efface le bit 1 de poids 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 1 ; 12 en contient donc deux. C’est aussi rapide que la règle de décalage et utilise le même remplissage de gauche à droite.
Est-ce que je peux utiliser une fonction popcount intégrée ?
La plupart des langages en ont une, comme Integer.bitCount en Java ou __builtin_popcount en C et C++, et l’appeler pour chaque nombre donne une réponse correcte. Les recruteurs demandent généralement la version sans cette fonction, car l’objectif du problème est de réutiliser les réponses que vous avez déjà calculées. La récurrence fonctionne également dans les langages qui ne disposent pas d’une telle fonction.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def countBits(n):
# Écrivez le code iciCas 1
Cas 2
Entrée
n = 2
Attendu
[0, 1, 1]