# LeetCode Notes: Counting Bits

## Question

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

Example 1:

Input: n = 2

Output: [0,1,1]

Explanation:

0 --> 0

1 --> 1

2 --> 10

Example 2:

Input: n = 5

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

Explanation:

0 --> 0

1 --> 1

2 --> 10

3 --> 11

4 --> 100

5 --> 101

Constraints:

• 0 <= n <= 105

• It is very easy to come up with a solution with a runtime of `O(n log n)`. Can you do it in linear time `O(n)` and possibly in a single pass?
• Could you solve it in `O(n)` space complexity?
• Can you do it without using any built-in function (i.e., like `__builtin_popcount` in C++)?

## Solution One

Analysis:

Get each number in a loop, convert it to binary, use regular expressions to find out how many numbers `1` in it, and then store it in the result array

Code:

``````/**
* @param {number} n
* @return {number[]}
*/
var countBits = function(n) {
// Store the result
const result = [];

// loop to get each number
for(let i = 0; i <= n; i++){
// Core method: Convert decimal numbers to binary, and match the number of digits 1
const matchOne = (i).toString(2).match(/1/g)
// If we get an array of matching values, we return the number of matches, otherwise we return 0 directly
result.push(matchOne? matchOne.length: 0)
}

// return result
return result
};

``````

## Solution Two

Analysis:

To upgrade to the first solution, use the `map` method on the newly created array to quickly get an array, and the internal processing of the function is still the same as above

Code:

``````/**
* @param {number} n
* @return {number[]}
*/
var countBits = function(n) {
// Create an array of n+1 length and traverse the array
return new Array(n+1).fill(0).map((item,i)=>{
// The number of regular matches 1
const matchOne = (i).toString(2).match(/1/g)
return matchOne? matchOne.length: 0
})
};
``````