Counting Bits
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]
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).