Counting Bits
Given an integer n, return an array bits of length n + 1 where bits[i] is the number of 1 bits in the binary representation of i, for every i from 0 to n.
Aim for O(n) time: one pass that reuses earlier answers instead of counting each number's bits from scratch.
Constraints
0 <= n <= 10^5
Examples
Example 1
Input: n = 4 Output: [0,1,1,2,1]
0, 1, 10, 11, 100 in binary have 0, 1, 1, 2 and 1 set bits.
Example 2
Input: n = 7 Output: [0,1,1,2,1,2,2,3]
From 4 (100) to 7 (111), each count is 1 more than the count for the same number without its top bit (0 to 3).
Example 3
Input: n = 0 Output: [0]
Only the number 0, which has no set bits.
JavaScript you'll use: Bitwise operators Arrays: create, read, update
/**
* @param {number} n
* @return {number[]}
*/
function countBits(n) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.