# Counting Bits II

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

## We'll cover the following

## Introduction

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

## Problem Statement

Write a program to return an array of number 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,

If a number has 2 set bits, then the while loop runs two times.

If a number has 4 set bits, then the while loop runs four times.

### Algorithm

**Steps:**

- Outer loop runs for
`(n+1)`

time to store the number of`1`

bits present every number from`0`

to`(n+1)`

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

present in each number

### Code

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.