bin()For each number from 0 to n, convert it to binary using bin() and count the '1' characters. Simple and straightforward.
Use the recurrence ans[i] = ans[i >> 1] + (i & 1). The number of 1-bits in i equals the number of 1-bits in i right-shifted by 1 (which removes the last bit) plus the value of the last bit itself. This builds the result in a single pass using previously computed values.
""" 0338.1 - Solution 1 - Brute Force using bin() """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def countBits(self, n: int) -> List[int]:
"""Counting Bits Function"""
ans = []
for i in range(n + 1):
ans.append(bin(i).count('1'))
return ans
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().countBits(2)) # [0, 1, 1]
print(Solution().countBits(5)) # [0, 1, 1, 2, 1, 2]
print(Solution().countBits(0)) # [0]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0338.2 - Solution 2 - Dynamic Programming (Bit Shift) """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def countBits(self, n: int) -> List[int]:
"""Counting Bits Function"""
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i >> 1] + (i & 1)
return ans
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().countBits(2)) # [0, 1, 1]
print(Solution().countBits(5)) # [0, 1, 1, 2, 1, 2]
print(Solution().countBits(0)) # [0]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()