338. Counting Bits

Problem Statement

LeetCode: https://leetcode.com/problems/counting-bits/

What we have to do: Given an integer, we need to count number of 1’s for each integer starting from given integer to 0. Return an array of integer representing number of 1’s for each integer value.

Solution

There are 3 methods to solve this problem:

1. The Bitwise way
2. Simple and Standard Method
3. Efficient Bitwise Method

Code Repo: https://github.com/mrunalnshah/Algorithms/tree/main/00_Bits-and-Computers/Arena/0338_Counting-Bits

Python Solution

Python Solution: https://github.com/mrunalnshah/Algorithms/tree/main/00_Bits-and-Computers/Arena/0338_Counting-Bits/Python

Method 1: The Bitwise way Code

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)  
 
        while n > 0:
            ans[n] = Solution.count(n)
            n -= 1
        return ans
 
    @staticmethod
    def count(n: int) -> int:
        count = 0
  
        while n > 0:
            if n & 1:
                count += 1
            n = n >> 1
        return count

Method 2: The Simple and Standard way Code

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
 
        while n > 0:
            ans[n] = bin(n).count('1')
            n -= 1
        return ans	

Method 3: The Efficient Bitwise way Code

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
 
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)
  
        return ans