Problem Statement in English

You’re given an integer n. Your task is to return the total number of $1$s in the binary representation of all numbers in the range $[1, n]$.

Step 1: Extract last bit from n

  • Step 1.1: Use a bitwise AND operation to find if the last bit is $0$ or $1$:
    If we use a bitwise AND between a number and $1$, we end up with $0$ if the last bit of the number is $0$, and $1$ otherwise. For example: - 4 & 1 = 0, as $(4)_2 = 100$, and $(1)_2 = 1$. When we use bitwise AND, we get $0$. - 7 & 1 = 1, as $(7)_2 = 111$, and $(1)_2 = 1$. When we use bitwise AND, we get $1$.

  • Step 1.2: Perform a right shift operation on n:
    This removes the last bit from n.

Step 2: Repeat until n is $0$

  • Step 2.1: We need to have removed all the bits from n:

Step 3: Store the answer in arr

Step 4: Repeat for all numbers in the range $[1,n]$

Solution in Python


class Solution:
    def countBits(self, n: int) -> List[int]:
        arr = []

        def count(num):
            ans = 0
            while num > 0:
                if num & 1 == 1:
                    ans += 1
                num = num >> 1
            arr.append(ans)

        for i in range(n + 1):
            count(i)

        return arr

Complexity

  • Time: $O(n)$
    Since we only process $n$ integers at most.

  • Space: $O(n)$
    Since we store $n$ integers at most in arr.

And we are done.