DEV Community

Cover image for LeetCode Meditations: Counting Bits
Eda
Eda

Posted on • Originally published at rivea0.github.io

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
Enter fullscreen mode Exit fullscreen mode

Or:

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]

Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
Enter fullscreen mode Exit fullscreen mode

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));
Enter fullscreen mode Exit fullscreen mode

...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;
});
Enter fullscreen mode Exit fullscreen mode

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++;
}
Enter fullscreen mode Exit fullscreen mode

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;
  });
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

Time and space complexity

Counting the set bits has log nlog \ n 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 nn is log nlog \ n ).
However, we also do it nn times, so overall, the time complexity will be O(n log n)O(n \ log \ n) .

The space complexity is O(n)O(n) as the need for space for our result array increases as nn increases.


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

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay