#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 ↗

Approach: Dynamic Programming / Bitwise

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

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

O(n) O(n)

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