Counting Bits

Try to solve the Counting Bits problem.

We'll cover the following

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement#

For a given positive integer, n, your task is to return an array of length $n+1$ such that for each $x$ where $0 \leq x \leq n$ , result[x] is the count of $1$ s in the binary representation of $x$ .

Constraints:

$0 \leq n \leq 10^5$

Examples#

1 of 2

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Counting Bits

What will be the output if $n = 6$ ?

$[0, 1, 1, 2, 1, 2, 2]$

$[0, 1, 1, 2, 1, 1, 2]$

$[0, 1, 2, 2, 1, 2, 1]$

Question 1 of 40 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Create an empty array of length $n + 1$ that will be used to store the results of the subproblems.

Starting from $0$ up to $n$ , calculate the binary representation of each number.

Count the number of 1s in each binary representation, and store them at their specified index in the resultant array.

Once the iteration is complete, return the result stored in the array.

Try it yourself#

Implement your solution in the following coding playground.

Python

usercode > main.py

def counting_bits(n):
    
    # Replace this placeholder return statement with your code
    return []

d

Enter to Rename, Shift+Enter to Preview

Input #1

Counting Bits

Solution: N-th Tribonacci Number

Solution: Counting Bits