Counting Bits

Easy

Problem

For every i from 0 to n, return the number of 1 bits in i's binary form. Aim for O(n) overall.

Example 1

Input:  n = 5
Output: [0, 1, 1, 2, 1, 2]

Test cases

Case 1

Input:    2
Expected: [0,1,1]

Case 2

Input:    5
Expected: [0,1,1,2,1,2]

Case 3

Input:    0
Expected: [0]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. DP on i >> 1

Time O(n)Space O(n) output

i has the same bits as i >> 1 plus its lowest bit.

function countBits(n) {
const res = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) res[i] = res[i >> 1] + (i & 1);
return res;
}

Also valid: res[i] = res[i & (i − 1)] + 1 (drop the lowest set bit).