Counting Bits II

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.