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.
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 ibitCounting(2);
// → [0, 1, 1]
// 0 = 0b0 → 0 bits
// 1 = 0b1 → 1 bit
// 2 = 0b10 → 1 bitbitCounting(5);
// → [0, 1, 1, 2, 1, 2]
// 3 = 0b11 → 2 bits
// 4 = 0b100 → 1 bit
// 5 = 0b101 → 2 bits0 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.n is always a non-negative integer. You don't need to handle negatives, floats, or non-numbers.1, 2, 4, 8, …) has exactly one set bit, so its entry is always 1.O(n log n); aim for the O(n) solution that reuses earlier counts.You'll fill an array where each slot holds the number of 1-bits in its own index, and the key move is computing each entry from one you already finished — not from scratch.
A number's binary form is a string of 0s and 1s. The count of 1s in it is called the population count, or "popcount" — it shows up everywhere from hashing and error-correcting codes to chess engines counting pieces on a board. Here you compute the popcount of every integer from 0 to n and return them in an array, so result[i] is the popcount of i.
The obvious approach counts each number's bits on its own. The good approach notices that the numbers aren't independent: the popcount of i is almost the popcount of a smaller number you've already solved. That overlap is what turns this from O(n log n) into O(n).
Write out the numbers 0 through 7 in binary and count their 1s. The output array is just that last column read top to bottom.
The insight that makes this fast: look at any number's binary form and chop off its last bit. What remains is that number divided by two, rounded down — which in bit terms is i >> 1 (a right shift). The bits of i >> 1 are exactly the bits of i minus the one you chopped off. So the popcount of i is the popcount of i >> 1, plus whatever that last bit was — 0 or 1.
The direct translation of the prompt: for each i from 0 to n, count its bits from scratch. The simplest way to count bits is to repeatedly test the lowest bit and shift right until the number is gone.
function bitCounting(n) {
const result = [];
for (let i = 0; i <= n; i++) {
let count = 0;
let x = i;
while (x > 0) {
count += x & 1; // add 1 if the lowest bit is set, else 0
x >>= 1; // drop the lowest bit and move on
}
result.push(count);
}
return result;
}This is correct — it returns exactly the right array. The problem is the inner while loop. For each number i it runs once per bit, which is about log i iterations. Summed over all n + 1 numbers, that's O(n log n) total work. You also recompute things you already know: when you reach i = 6 (110), you count its three positions even though you finished i = 3 (11) — which holds two of those exact bits — a few steps earlier. The naive version throws that finished work away.
Build the array left to right. By the time you compute result[i], the entry for i >> 1 is already sitting in the array — because i >> 1 is always strictly smaller than i for i >= 1. So you read it in O(1) and add the low bit.
function bitCounting(n) {
// result[i] will hold the popcount of i. Length is n + 1 because
// we include both endpoints, 0 and n.
const result = new Array(n + 1).fill(0);
// result[0] is already 0 (zero has no set bits), so start at 1.
for (let i = 1; i <= n; i++) {
// i >> 1 is i with its lowest bit chopped off (i.e. Math.floor(i / 2)),
// and it's always < i, so result[i >> 1] is already filled in.
// (i & 1) is the bit we chopped off: 1 if i is odd, 0 if even.
result[i] = result[i >> 1] + (i & 1);
}
return result;
}
module.exports = { bitCounting };The shift from the naive version is the inner loop disappearing. Instead of walking every bit of i, you reuse the count of i >> 1 — a number you finished earlier in the same pass — and adjust by the single bit that differs. Each number now costs one array read, one bitwise-and, and one addition: constant work per index, so O(n) overall. The new Array(n + 1) sizing bakes the length contract straight into the allocation, and starting the loop at i = 1 lets result[0] = 0 stand as the base case.
Trace bitCounting(5). Start with result = [0, 0, 0, 0, 0, 0] (length 6), and result[0] stays 0.
i = 1 (binary 1): i >> 1 = 0, result[0] = 0, i & 1 = 1 → result[1] = 0 + 1 = 1
i = 2 (binary 10): i >> 1 = 1, result[1] = 1, i & 1 = 0 → result[2] = 1 + 0 = 1
i = 3 (binary 11): i >> 1 = 1, result[1] = 1, i & 1 = 1 → result[3] = 1 + 1 = 2
i = 4 (binary 100): i >> 1 = 2, result[2] = 1, i & 1 = 0 → result[4] = 1 + 0 = 1
i = 5 (binary 101): i >> 1 = 2, result[2] = 1, i & 1 = 1 → result[5] = 1 + 1 = 2
return [0, 1, 1, 2, 1, 2]
Watch i = 5. Its binary is 101. Shifting right gives 10 (the number 2), whose popcount we settled three steps earlier as 1. The chopped-off low bit was 1, so result[5] = result[2] + 1 = 2. We never re-examined the high bits of 5 — they were already accounted for inside result[2]. That reuse, repeated for every index, is the whole speedup.
n + 1, not n. The array is inclusive of both 0 and n, so it has n + 1 slots. new Array(n) would be one short and result[n] would be undefined. Allocate new Array(n + 1).i >> 1 < i, so result[i >> 1] is computed before result[i]. If you iterated i from high to low, you'd read entries that are still 0 and get garbage. Fill left to right.i & 1 is the new low bit, not the whole remainder. A common slip is writing result[i] = result[i >> 1] + i or + (i % 2 + something). The only thing the shift drops is the single lowest bit, recovered as i & 1 (equivalently i % 2). Add exactly that — 0 or 1.n = 0 must return [0], not []. With new Array(1).fill(0) you get [0], and the loop for (i = 1; i <= 0) never runs, so the base case stands. Don't special-case it with an early return [] — that's the wrong answer.i <= n, not i < n. With i < n you'd never compute result[n] and the last slot would stay 0. Inclusive bound.>>, not >>>, but it doesn't matter here. For non-negative i the signed (>>) and unsigned (>>>) right shifts behave identically. Since the prompt guarantees non-negative input, either works; >> reads more naturally.i & (i - 1) clears the lowest set bit in one step. That gives a second O(n) recurrence, result[i] = result[i & (i - 1)] + 1, since the cleared value has exactly one fewer set bit. Used on its own (without the table), it counts a single number's bits in as many iterations as that number has set bits — faster than checking every bit position when bits are sparse.result[i] = result[i & (i - 1)] + 1 — both this and the i >> 1 version are textbook dynamic-programming recurrences for this problem (it's LeetCode 338). They differ only in which smaller, already-solved number they reuse: i >> 1 reuses "i without its last bit," while i & (i - 1) reuses "i without its last set bit." Both are O(n).popcnt — modern CPUs have a single instruction that returns a number's popcount directly. Languages expose it as a builtin (__builtin_popcount in GCC/Clang, Integer.bitCount in Java, int.bit_count() in Python 3.10+). JavaScript has no direct equivalent, but engines may compile a tight bit-counting loop down to it. When you only need one number's popcount, that's the fastest path; this DP wins specifically when you need all counts from 0 to n.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
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.
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 ibitCounting(2);
// → [0, 1, 1]
// 0 = 0b0 → 0 bits
// 1 = 0b1 → 1 bit
// 2 = 0b10 → 1 bitbitCounting(5);
// → [0, 1, 1, 2, 1, 2]
// 3 = 0b11 → 2 bits
// 4 = 0b100 → 1 bit
// 5 = 0b101 → 2 bits0 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.n is always a non-negative integer. You don't need to handle negatives, floats, or non-numbers.1, 2, 4, 8, …) has exactly one set bit, so its entry is always 1.O(n log n); aim for the O(n) solution that reuses earlier counts.You'll fill an array where each slot holds the number of 1-bits in its own index, and the key move is computing each entry from one you already finished — not from scratch.
A number's binary form is a string of 0s and 1s. The count of 1s in it is called the population count, or "popcount" — it shows up everywhere from hashing and error-correcting codes to chess engines counting pieces on a board. Here you compute the popcount of every integer from 0 to n and return them in an array, so result[i] is the popcount of i.
The obvious approach counts each number's bits on its own. The good approach notices that the numbers aren't independent: the popcount of i is almost the popcount of a smaller number you've already solved. That overlap is what turns this from O(n log n) into O(n).
Write out the numbers 0 through 7 in binary and count their 1s. The output array is just that last column read top to bottom.
The insight that makes this fast: look at any number's binary form and chop off its last bit. What remains is that number divided by two, rounded down — which in bit terms is i >> 1 (a right shift). The bits of i >> 1 are exactly the bits of i minus the one you chopped off. So the popcount of i is the popcount of i >> 1, plus whatever that last bit was — 0 or 1.
The direct translation of the prompt: for each i from 0 to n, count its bits from scratch. The simplest way to count bits is to repeatedly test the lowest bit and shift right until the number is gone.
function bitCounting(n) {
const result = [];
for (let i = 0; i <= n; i++) {
let count = 0;
let x = i;
while (x > 0) {
count += x & 1; // add 1 if the lowest bit is set, else 0
x >>= 1; // drop the lowest bit and move on
}
result.push(count);
}
return result;
}This is correct — it returns exactly the right array. The problem is the inner while loop. For each number i it runs once per bit, which is about log i iterations. Summed over all n + 1 numbers, that's O(n log n) total work. You also recompute things you already know: when you reach i = 6 (110), you count its three positions even though you finished i = 3 (11) — which holds two of those exact bits — a few steps earlier. The naive version throws that finished work away.
Build the array left to right. By the time you compute result[i], the entry for i >> 1 is already sitting in the array — because i >> 1 is always strictly smaller than i for i >= 1. So you read it in O(1) and add the low bit.
function bitCounting(n) {
// result[i] will hold the popcount of i. Length is n + 1 because
// we include both endpoints, 0 and n.
const result = new Array(n + 1).fill(0);
// result[0] is already 0 (zero has no set bits), so start at 1.
for (let i = 1; i <= n; i++) {
// i >> 1 is i with its lowest bit chopped off (i.e. Math.floor(i / 2)),
// and it's always < i, so result[i >> 1] is already filled in.
// (i & 1) is the bit we chopped off: 1 if i is odd, 0 if even.
result[i] = result[i >> 1] + (i & 1);
}
return result;
}
module.exports = { bitCounting };The shift from the naive version is the inner loop disappearing. Instead of walking every bit of i, you reuse the count of i >> 1 — a number you finished earlier in the same pass — and adjust by the single bit that differs. Each number now costs one array read, one bitwise-and, and one addition: constant work per index, so O(n) overall. The new Array(n + 1) sizing bakes the length contract straight into the allocation, and starting the loop at i = 1 lets result[0] = 0 stand as the base case.
Trace bitCounting(5). Start with result = [0, 0, 0, 0, 0, 0] (length 6), and result[0] stays 0.
i = 1 (binary 1): i >> 1 = 0, result[0] = 0, i & 1 = 1 → result[1] = 0 + 1 = 1
i = 2 (binary 10): i >> 1 = 1, result[1] = 1, i & 1 = 0 → result[2] = 1 + 0 = 1
i = 3 (binary 11): i >> 1 = 1, result[1] = 1, i & 1 = 1 → result[3] = 1 + 1 = 2
i = 4 (binary 100): i >> 1 = 2, result[2] = 1, i & 1 = 0 → result[4] = 1 + 0 = 1
i = 5 (binary 101): i >> 1 = 2, result[2] = 1, i & 1 = 1 → result[5] = 1 + 1 = 2
return [0, 1, 1, 2, 1, 2]
Watch i = 5. Its binary is 101. Shifting right gives 10 (the number 2), whose popcount we settled three steps earlier as 1. The chopped-off low bit was 1, so result[5] = result[2] + 1 = 2. We never re-examined the high bits of 5 — they were already accounted for inside result[2]. That reuse, repeated for every index, is the whole speedup.
n + 1, not n. The array is inclusive of both 0 and n, so it has n + 1 slots. new Array(n) would be one short and result[n] would be undefined. Allocate new Array(n + 1).i >> 1 < i, so result[i >> 1] is computed before result[i]. If you iterated i from high to low, you'd read entries that are still 0 and get garbage. Fill left to right.i & 1 is the new low bit, not the whole remainder. A common slip is writing result[i] = result[i >> 1] + i or + (i % 2 + something). The only thing the shift drops is the single lowest bit, recovered as i & 1 (equivalently i % 2). Add exactly that — 0 or 1.n = 0 must return [0], not []. With new Array(1).fill(0) you get [0], and the loop for (i = 1; i <= 0) never runs, so the base case stands. Don't special-case it with an early return [] — that's the wrong answer.i <= n, not i < n. With i < n you'd never compute result[n] and the last slot would stay 0. Inclusive bound.>>, not >>>, but it doesn't matter here. For non-negative i the signed (>>) and unsigned (>>>) right shifts behave identically. Since the prompt guarantees non-negative input, either works; >> reads more naturally.i & (i - 1) clears the lowest set bit in one step. That gives a second O(n) recurrence, result[i] = result[i & (i - 1)] + 1, since the cleared value has exactly one fewer set bit. Used on its own (without the table), it counts a single number's bits in as many iterations as that number has set bits — faster than checking every bit position when bits are sparse.result[i] = result[i & (i - 1)] + 1 — both this and the i >> 1 version are textbook dynamic-programming recurrences for this problem (it's LeetCode 338). They differ only in which smaller, already-solved number they reuse: i >> 1 reuses "i without its last bit," while i & (i - 1) reuses "i without its last set bit." Both are O(n).popcnt — modern CPUs have a single instruction that returns a number's popcount directly. Languages expose it as a builtin (__builtin_popcount in GCC/Clang, Integer.bitCount in Java, int.bit_count() in Python 3.10+). JavaScript has no direct equivalent, but engines may compile a tight bit-counting loop down to it. When you only need one number's popcount, that's the fastest path; this DP wins specifically when you need all counts from 0 to n.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.