LeetCode Meditations: Counting Bits

The description for Counting Bits says:

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

For example:

Input: n = 2

Output: [0, 1, 1]



Explanation:

0 --> 0

1 --> 1

2 --> 10

Or:

Input: n = 5

Output: [0, 1, 1, 2, 1, 2]



Explanation:

0 --> 0

1 --> 1

2 --> 10

3 --> 11

4 --> 100

5 --> 101

The problem wants us to get the number of 1s of the binary representation of each number from 0 up to n.

The first solution I came up with was to create an array of length n + 1, fill it with values from 0 to n in binary...

const arr = Array.from({ length: n + 1 }, (_, i) => i.toString(2));

...and map each one to the number of 1 bits it has:

arr.map(j => {

  let result = 0;

  let binaryNumber = parseInt(j, 2);

  while (binaryNumber > 0) {

    binaryNumber &= binaryNumber - 1;

    result++;

  }

  return result;

});

Note that in the previous problem, we used a technique to count the number of 1 bits (or calculate its Hamming weight) — it's simply decreasing one lesser value from the number until it reaches 0:

let numberOf1Bits = 0;

while (binaryNumber > 0) {

  binaryNumber &= binaryNumber - 1;

  numberOf1Bits++;

}

We can chain the methods, and overall, the solution looks like this:

function countBits(n: number): number[] {

  return Array.from({ length: n + 1 }, (_, i) => i.toString(2)).map(j => {

    let result = 0;

    let binaryNumber = parseInt(j, 2);

    while (binaryNumber > 0) {

      binaryNumber &= binaryNumber - 1;

      result++;

    }

    return result;

  });

}

Or, we can write it more explicitly, pushing each count to the result array:

function countBits(n: number): number[] {

  let result = [];

  for (let i = 0; i <= n; i++) {

    let binaryNum = parseInt(i.toString(2), 2);

    let count = 0;

    while (binaryNum > 0) {

      binaryNum &= binaryNum - 1;

      count++;

    }

    result.push(count);

  }



  return result;

}

Time and space complexity

Counting the set bits has


$logn$

time complexity (in the worst case when all bits are set, the loop will run the number of bits in binaryNumber — the number of bits of the binary representation of number

$n$

is

$logn$

).

However, we also do it

$n$

times, so overall, the time complexity will be

$O(nlogn)$

.

The space complexity is

$O(n)$

as the need for space for our result array increases as

$n$

increases.

Next up, we'll take a look at Reverse Bits. Until then, happy coding.