Overview

Given a non-negative integer n, return an array result of length n + 1 where result[i] is the number of 1s in the binary representation of i.

This is also known as the popcount or Hamming weight for each number from 0 to n.

Constraints

• 0 <= n <= 100,000
• Return an array of length n + 1.
• Aim for O(n) time — avoid counting bits from scratch for each number.

Examples

countBits(5);
// => [0, 1, 1, 2, 1, 2]
// 0: 000 -> 0
// 1: 001 -> 1
// 2: 010 -> 1
// 3: 011 -> 2
// 4: 100 -> 1
// 5: 101 -> 2

countBits(2);
// => [0, 1, 1]

Solution

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

Resources

• Counting Bits — LeetCode
• Hamming Weight — Wikipedia