#146 Easy Time O(n) Space O(n) Animated

Counting Bits

Return array of number of 1 bits for every number 0 to n.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Bitwise state reduction

Use a bit operation to retain only the information the problem needs while discarding the rest.

Approach: Dynamic Programming / Bitwise

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Use a bit operation to retain only the information the problem needs while discarding the rest.

Common Pitfall

Parenthesize shifts and masks, especially when mixing comparison or arithmetic operators.

Description

Return array of number of 1 bits for every number 0 to n.

Constraints

Time Complexity: O(n)
Space Complexity: O(n)

Solution — Dynamic Programming / Bitwise

TimeO(n) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Choose the bitwise identity.
Initialize the accumulator or mask.
Apply the operation per value or bit.
Interpret the resulting bits.

def countBits(n):
    dp = [0] * (n + 1)
    offset = 1
    
    for i in range(1, n + 1):
        if offset * 2 == i:
            offset = i
        dp[i] = 1 + dp[i - offset]
        
    return dp

Number of 1 Bits

Reverse Bits

Counting Bits

Steps

Description

Constraints

Tags

Solution — Dynamic Programming / Bitwise