# 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.

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

1. The outer loop runs for `(n+1)` time to store the number of `1` bits present every number from `0` to `(n+1)`.
2. The inner loop uses Brian Kernighan’s algorithm to find the number of `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.

Coding Interview QuestionsData Structures and AlgorithmsBit Manipulation

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

## Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

## Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

## Bit Manipulation Course Overview

Overview In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies. To kick things