338.Counting_Bits(Easy).md

338. Counting Bits (Easy)

Date and Time: Nov 8, 2024, 15:50 (EST)

Link: https://leetcode.com/problems/counting-bits/

Question:

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 1:

Input: n = 2

Output: [0,1,1]

Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5

Output: [0,1,1,2,1,2]

Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints:

• 0 <= n <= 10^5

Walk-through:

1. We need to find how many 1s need for each i in range(1, n+1).

2. The way we find that is to i & 1 to know the last bit is 1 or not. We do res[i >> 1] to move the bit to the right by 1, so we know how many 1s we have from before.

We use dp to keep track of all previous number of bit 1.

Python Solution:

class Solution:
    def countBits(self, n: int) -> List[int]:
        # Find how many 1s for range(0, n)
        # i & 1 to know if the last bit is 1 or not
        # get how many 1s of i >> 1 (divide i // 2)

        # 5: 0101
        # 5 // 2 = 2: 0010
        # 2 // 2: 0001

        # [0000, 0001, 0010, 0011, 0100, 0101]
        # [0, 1, 1, 2, 1, 2]

        # TC: O(n), SC: O(n)
        res = [0] * (n+1)
        for i in range(1, n+1):
            res[i] = res[i >> 1] + (i & 1)
        return res

Time Complexity: $O(n)$, n is the range(0, n).
Space Complexity: $O(n)$