# Thought process & DP solution in JS

• My thought process:

First I wrote down the binary representation of the first few integers

``````[0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010]

``````

then I circled the numbers that are a power of 2 (10, 100, 1000, ...).
After that, I noticed that all other numbers can be expressed as the sum of (power of 2 smaller than itself + some integer smaller than itself).

For example number 9 = (8 + 1)
The number of 1 bit for 9 corresponds to (number of bit for 8 + number of bit for 1).
If the number is a power of 2, then the number of 1 bit is one (the most significant bit).
With this, we can use a bottom-up approach to generate the array.
I implemented this with JS.

``````/**
* @param {number} num
* @return {number[]}
*/
const countBits = (num) => {
const bits = [0];
for (let i = 1; i <= num; i++) {
const exp = Math.floor(Math.log2(i));
const pow = Math.pow(2, exp);
const other = i - pow;
if (other === 0) {
bits.push(1);
} else {
const bitCount = 1 + bits[other];
bits.push(bitCount);
}
}
return bits;
};
``````

• @kenhibino this was really helpful, thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.