Bit Counting

Every non-negative integer has a binary form, and the number of 1s in that form is its population count (or "popcount"). Given a number n, you return an array where the entry at each index i is the popcount of i. So result[3] is the number of set bits in 3 (binary 11, two bits), result[4] is the popcount of 4 (binary 100, one bit), and so on for every integer from 0 through n.

The naive route — count the bits of each number independently — works but does redundant work. The interesting version reuses the counts you've already computed.

Signature

function bitCounting(n: number): number[];
// n  — a non-negative integer
// returns an array `result` of length n + 1,
// where result[i] = number of 1-bits in the binary representation of i

Examples

bitCounting(2);
// → [0, 1, 1]
// 0 = 0b0   → 0 bits
// 1 = 0b1   → 1 bit
// 2 = 0b10  → 1 bit

bitCounting(5);
// → [0, 1, 1, 2, 1, 2]
// 3 = 0b11  → 2 bits
// 4 = 0b100 → 1 bit
// 5 = 0b101 → 2 bits

Notes

• 0-indexed and inclusive — the array covers every integer from 0 up to and including n, so its length is exactly n + 1.
• n = 0 — the smallest valid input. bitCounting(0) returns [0], since 0 has zero set bits.
• Non-negative input — n is always a non-negative integer. You don't need to handle negatives, floats, or non-numbers.
• Powers of two — any power of two (1, 2, 4, 8, …) has exactly one set bit, so its entry is always 1.
• Target complexity — a correct answer is easy in O(n log n); aim for the O(n) solution that reuses earlier counts.