LC 338 - 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 <= 105

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++)?

Links

Question here and solution here

Solution

concept

This is a DP problem in the sense we have to reuse the results computed previously.

0 -> 0000 -> 0
1 -> 0001 -> 1 + dp[n-1] = 1
2 -> 0010 -> 1 + dp[n-2] = 1
3 -> 0011 -> 1 + dp[n-2] = 2
4 -> 0100 -> 1 + dp[n-4] = 1
5 -> 0101 -> 1 + dp[n-4] = 2
6 -> 0110 -> 1 + dp[n-4] = 2
7 -> 0111 -> 1 + dp[n-4] = 3
8 -> 1000 -> 1 + dp[n-8] = 1

Note that n is our current number and whenever we reach a threshold of power of 2, we have to increase the offset. (i.e. n-2, n-4 etc) This offset is the largest significant bit so far, because since we have upgrade into the largest significant bit, we basically reuse the previous computed value for the other bits i.e. when we ready 0100, we see that the 3rd bit is 1 but the 00 on the right is just from previous value.

code

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

        for i in range(1, n + 1):
            if offset * 2 == i:
                offset = i
            dp[i] = 1 + dp[i - offset]
        return dp

class Solution:
	"""
	brute force
	"""
    def countBits(self, n: int) -> List[int]:
        res = []
        for num in range(n + 1):
            one = 0
            for i in range(32):
                if num & (1 << i):
                    one += 1
            res.append(one)
        return res

Complexity

time: $O(n)$
space: $O(n)$