338. Counting Bits

Easy

---

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

Follow up:

• It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?

• Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Solution 1:

Using solution of Problem 191: Number of 1 Bits

class Solution:
    # O(nlogn)
    def countBits(self, n: int) -> List[int]:
        result = []
        for num in range(n+1):
            count = self.bit_count(num)
            result.append(count)
        return result
    
    def bit_count(self, n: int) -> int:
        count = 0
        while n != 0:
            count = count + (n&1)
            n = n >> 1
        return count

Solution 2:

Since multiplying by 2 just adds a zero, then any number and its double will have the same number of 1's. Likewise, doubling a number and adding one will increase the count by exactly 1. Or:

• countBits(N) = countBits(2N)

• countBits(N)+1 = countBits(2N+1)

Thus we can see that any number will have the same bit count as half that number, with an extra one if it's an odd number. We iterate through the range of numbers and calculate each bit count successively in this manner:

for i in range(num):
    counter[i] = counter[i // 2] + i % 2

Complexity : O(n)

class Solution:
    def countBits(self, n: int) -> List[int]:
        count = [0]
        for num in range(1, n+1):
            count.append(count[num >> 1] + num%2)
        return count