Counting Bits

Easy · Bit Manipulation

Given a non-negative integer n, return a list of length n+1 where the value at each index i is the number of 1-bits in the binary representation of i. Index 0 always corresponds to the value 0.

Examples

Input:  n = 2
Output: [0, 1, 1]
Why:    0 has zero 1-bits, 1 has one 1-bit, and 2 (10 in binary) has one 1-bit.

Input:  n = 5
Output: [0, 1, 1, 2, 1, 2]
Why:    5 is 101 in binary which has two 1-bits, 3 is 11 which has two 1-bits, and so on for each index.

Input:  n = 0
Output: [0]
Why:    Only index 0 exists and it has zero 1-bits.

Constraints

0 <= n <= 10^5

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Counting Bits

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Counting Bits. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.