LeetCode 338: Counting Bits — Step-by-Step Visual Trace

#leetcode #algorithms #python #dynamicprogramming

Easy — Dynamic Programming | Bit Manipulation | Array

The Problem

Given an integer n, return an array where the i-th element represents the number of 1-bits in the binary representation of integer i for all numbers from 0 to n.

Approach

Use dynamic programming to build the result array incrementively. For any number i, the count of 1-bits equals the count for i//2 plus 1 if i is odd (i%2). This leverages the relationship between a number and its right-shifted version.

Time: O(n) · Space: O(n)

Code

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits_count = [0] * (num + 1)

        for i in range(1, num + 1):
            bits_count[i] = bits_count[i // 2] + (i % 2)

        return bits_count