Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0338 - Counting Bits
    0338 - Counting Bits
    0338 - Counting Bits
    0338 - Counting Bits

    0338 - Counting Bits

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/counting-bits/

    Solution 1 - Brute Force using bin()

    For each number from 0 to n, convert it to binary using bin() and count the '1' characters. Simple and straightforward.

    TimeComplexity:O(n⋅log⁡n)TimeComplexity: O(n \cdot \log n)TimeComplexity:O(n⋅logn)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)

    Solution 2 - Dynamic Programming (Bit Shift)

    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.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    """ 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()