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




</p>
<p>Or:<br>
</p>

<pre class="brush:php;toolbar:false">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:

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

Explanation:
0 --> 0
1 --> 1
2 --> 10

Time and space complexity

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

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

---

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

The above is the detailed content of LeetCode Meditations: Counting Bits. For more information, please follow other related articles on the PHP Chinese website!