Build an O(n) table of 1-bit counts for 0 through n
A permissions dashboard shows, for every role ID from 0 to n, how many permission bits that role has turned on. Role IDs are dense, so instead of counting bits for each ID from scratch, the dashboard precomputes a lookup table once.
Implement bitCountTable(n). It returns an array of length n + 1 where the value at index i is the number of 1 bits in the binary form of i.
bitCountTable(n) // => number[] of length n + 1
n is an integer from 0 to 1000000 (one million). Throw a RangeError for anything else: negative numbers, fractions, NaN, Infinity, numbers above one million, and non-numbers such as '8'.bitCountTable(0); // => [0]
bitCountTable(5); // => [0, 1, 1, 2, 1, 2]
// 0 1 10 11 100 101 (binary of each index)
bitCountTable(8); // => [0, 1, 1, 2, 1, 2, 2, 3, 1]
bitCountTable(-1); // throws RangeError
bitCountTable(2.5); // throws RangeError
Hint: how does the bit count of i relate to the bit count of i with its lowest bit dropped?