Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 <= i <= num calculate the number of 1's in their binary representation and return them as an array. Tags: Binary, Dynamic Programming
Try It!
Discussion
Video
Solution
class Solution:
def countBits(self, num: int) -> List[int]:
# numbers can be represented as 2n or 2n + 1
# numBits(2n) == numBits(n)
# numBits(2n + 1) == numBit(n) + 1
dp = [0 for i in range(num + 1)]
for i in range(1, num + 1):
dp[i] = dp[i // 2] + (i % 2)
# or with bit operators
# dp[i] = dp[i >> 1] + (i & 1)
return dp