LC338 - Counting Bits

Problem

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

Input: n = 2

Output: [0,1,1]

Explanation:

• 0 --> 0

• 1 --> 1

• 2 --> 10

Solution

Intuition

def countBits(self, n: int) -> List[int]:
	count = []
	for i in range(0, n+1):
		tmp = format(i, 'b')
		subcount = 0
		for char in tmp:
			if char == '1':
				subcount += 1
		count.append(subcount)
	return count

Dynamic Programming

The number of bits contains a repeating pattern when looking at the LSBs, so we can reuse the calculations to get linear time complexity.

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