# Solution For Counting Bits

Counting Bits is a problem on LeetCode that requires us to count the number of 1’s in the binary representation of a given integer from 0 to n.

For example, if n=5, we need to count the number of 1’s in binary representation of 0, 1, 2, 3, 4, and 5.

We can solve this problem using Dynamic Programming with Time complexity of O(n).

The Approach is to use the fact that the number of 1’s in binary representation of a number i is equal to the number of 1’s in binary representation of i/2 plus the last bit of i, which is 0 if i is even, and 1 if i is odd.

Algorithm:

1- Create an array dp of size n+1.

2- Initialize the first element dp with 0.

3- Traverse through the range from 1 to n, and perform the following.

a) If the current number is even, then the number of 1’s in its binary representation equals the number of 1’s in i/2, which is stored in dp[i/2].

b) If the current number is odd, then the number of 1’s in its binary representation equals the number of 1’s in i/2 plus 1, which is stored in dp[i/2] + 1.

4- Assign the value of dp[i] equal to the above calculated value.

5- Return the array dp as solution.

Python Code:

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

C++ Code:

`class Solution { public: vector<int> countBits(int n) { vector<int> dp(n+1, 0); for(int i=1; i<=n; i++){ if(i%2 == 0){ dp[i] = dp[i/2]; } else{ dp[i] = dp[i/2] + 1; } } return dp; } };`

This gives us the required solution to the problem.

## Step by Step Implementation For Counting Bits

```public class Solution {
public int[] countBits(int num) {

// create an array to store the number of bits for each number from 0 to num
int[] result = new int[num + 1];

// for each number from 0 to num
for (int i = 0; i <= num; i++) {

// initialize the number of bits to 0
int bits = 0;

// create a variable to store the current number
int n = i;

// while the current number is greater than 0
while (n > 0) {

// if the rightmost bit is 1
if ((n & 1) == 1) {

// increment the number of bits
bits++;
}

// right shift the current number
n = n >> 1;
}

// store the number of bits in the array
result[i] = bits;
}

// return the array
return result;
}
}```
```class Solution:
def countBits(self, num: int) -> List[int]:
# create an empty list to store the results
results = []

# loop through each number from 0 to num
for i in range(num+1):
# convert the number to binary
binary = bin(i)[2:]
# count the number of ones in the binary representation
count = binary.count("1")
# append the count to the results list
results.append(count)

# return the results list
return results```
```var countBits = function(num) {

// create an empty array to store the results
let results = [];

// loop through each number from 0 to num
for (let i = 0; i <= num; i++) {

// convert the number to binary
let binary = i.toString(2);

// count the number of ones in the binary representation
let ones = 0;
for (let j = 0; j < binary.length; j++) {
if (binary[j] === "1") {
ones++;
}
}

// add the number of ones to the results array
results.push(ones);
}

// return the results array
return results;
};```
```class Solution {
public:
vector countBits(int num) {
vector res(num+1, 0);
for(int i=1; i<=num; i++)
res[i] = res[i/2] + (i&1);
return res;
}
};```
```public class Solution {
public int[] CountBits(int num) {
int[] result = new int[num + 1];
for (int i = 1; i <= num; i++) {
result[i] = result[i >> 1] + (i & 1);
}
return result;
}
}

// This solution uses the fact that the number of 1 bits in a number is equal to the number of 1 bits in half the number, plus 1 if the number is odd.```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]