Counting Bits Program (Leetcode)

Counting Bits Program (Leetcode):

The Counting Bits program on LeetCode is a dynamic programming problem designed to calculate the number of 1 bits in the binary representation of all numbers from 0 to a given integer n. The goal is to efficiently generate an array where each element represents the count of set bits (1s) in the binary representation of its corresponding index. The dynamic programming approach involves observing patterns in binary numbers to determine the number of set bits. By using previously computed results and bitwise operations, the program optimally computes the count of set bits for each number in the range. This problem challenges programmers to develop efficient algorithms that minimize time complexity and memory usage while accurately counting the bits for large integers.

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 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

 

Constraints:

• 0 <= n <= 105

 

Follow up:

• It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time? O(n) and possibly in a single pass?
• Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Want to check about the Latest Electronic Devices: CompareKarein

class Solution:
    def countBits(self, num: int) -> List[int]:
        
        ans = [0] * (num + 1)
        for i in range(num + 1):
            if i % 2 == 0:
                ans[i] = ans[i//2]
            else:
                ans[i] = ans[i - 1] + 1
        return ans