deepSWE.io

Counting Bits

Bit ManipulationDynamic Programming

15 min

Problem Statement

Given an integer n, return an array ans of length n + 1 such that for each i (0 ≤ i ≤ n), ans[i] is the number of '1's in the binary representation of i.

Example

Example 1:

Input: n = 2

Output: [0,1,1]

Solution (Dynamic Programming)

This problem can be solved efficiently using dynamic programming. The key insight is that the number of '1's in the binary representation of a number i is related to the number of '1's in a smaller number.

Algorithm Steps

Create an array ans of size n + 1.
Initialize ans[0] = 0.
For each number i from 1 to n, the number of '1's is ans[i >> 1] + (i & 1).

ans array

Start: Initialize an array 'ans' of size n+1 with zeros.

Counting Bits Solution


class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)
        return ans