# Counting Bits II

This is an extension to the counting set bits problem, counting the number of set bits or 1's present in a number. In here we see solutions in Java, JavaScript, Cpp, and TypeScript.

## Table of Contents

This is an extension to the previous problem counting the number of set bits or 1's present in a number.

## Introduction

This is an extension of the previous counting set bits problem.

## Problem Statement

Write a program to return an array of numbers of 1’s in the binary representation of every number in the range `[0, n]`

.

```
Input: n = 6
Output: [0, 1, 1, 2, 1, 2, 2]
Explanation:
0 --> 0
1 --> 1
2 --> 1
3 --> 2
4 --> 1
5 --> 2
6 --> 2
```

## Solution

This is a faster execution as we use ** Brian Kernighan’s algorithm**.

In this approach, we count only the set bits. So,

- The while loop runs twice if a number has 2 set bits.
- The while loop runs four times if a number has 4 set bits.

### Algorithm

- The outer loop runs for
`(n+1)`

time to store the number of`1`

bits present every number from`0`

to`(n+1)`

. - The inner loop uses
to find the number of**Brian Kernighan’s algorithm**`1's`

present in each number

### Java

```
import java.util.Arrays;
class CountingBits {
private static int helper(int n) {
int count = 0;
while (n > 0) {
n &= (n - 1);
count++;
}
return count;
}
private static int[] countingBits(int n) {
int[] ans = new int[n + 1];
for (int i = 0; i <= n; i++) {
ans[i] = helper(i);
}
return ans;
}
public static void main(String[] args) {
int number = 6;
System.out.println("Result " + Arrays.toString(countingBits(number)));
}
}
// Output: Result [0, 1, 1, 2, 1, 2, 2]
```

### Python

```
def count_bits(n):
count = 0
while n > 0:
n &= (n - 1)
count += 1
return count
def counting_bits(n):
ans = [0] * (n + 1)
for i in range(n + 1):
ans[i] = count_bits(i)
return ans
n=6
print(counting_bits(n))
# output: Result [0, 1, 1, 2, 1, 2, 2]
```

### JavaScript

```
const helper = (n) => {
let count = 0;
while (n > 0) {
n &= (n - 1);
count++;
}
return count;
}
const countingBits = (n) => {
const ans = [];
for (let i = 0; i <= n; i++) {
ans[i] = helper(i);
}
return ans;
}
let number = 6;
console.log('Result:' , countingBits(number));
// Output: Result: [ 0, 1, 1, 2, 1, 2, 2 ]
```

### C++

```
#include <iostream>
#include <vector>
using namespace std;
int helper(int n){
int count = 0 ;
while(n) {
n = n & n-1;
count++;
}
return count;
}
int main() {
int number = 6;
for (int i = 0; i <= number; i++) {
cout << helper(i) << ",";
}
return 0;
}
// Output: 0,1,1,2,1,2,2,
```

### TypeScript

```
export const helper = (n: number): number => {
let count: number = 0;
while (n > 0) {
n &= (n - 1);
count++;
}
return count;
}
export const countingBits = (n: number): number[] => {
const ans: number[] = [];
for (let i = 0; i <= n; i++) {
ans[i] = helper(i);
}
return ans;
}
let number: number = 6;
console.log('Result: [' + countingBits(number)+']');
// Output: Result: [0,1,1,2,1,2,2]
```

## Complexity Analysis

### Time complexity

{ O(n+1) * O(Set Bit count)} / {O(n+1) * O(1)} in simple terms

The time taken is proportional to set bits in binary representation and the outer loop, which runs `(n+1)`

times.

So, the time taken is O(n+1) => `O(n)`

The inner loop or `helper`

function run time depends on the number of set bits in n. In the worst case, all bits in n are 1-bits. In the case of a 32-bit integer, the run time is `O(32)`

or `O(1)`

.

### Space complexity

The space complexity is `O(1)`

. No additional space is allocated.

## Gopi Gorantala Newsletter

Join the newsletter to receive the latest updates in your inbox.