Developers

Counting Bits

EasyBits and mathAlso known as LeetCode 338

You get a non-negative integer n. Return a list of length n + 1 where entry i is the number of 1 bits in the binary representation of i.

Counting each number separately is allowed, but try to do the whole list in O(n) total time, reusing answers you have already computed.

Examples

Input n = 2
Output [0, 1, 1]
0 is 0, 1 is 1, 2 is 10.
Input n = 5
Output [0, 1, 1, 2, 1, 2]
Input n = 0
Output [0]

Constraints

  • 0 <= n <= 100,000

Stuck? Take one hint at a time

Common mistakes
  • Returning a list of length n instead of n + 1, so the last number is missing.
  • Using the answer at i - 1 plus one, which is wrong: 3 (11) to 4 (100) drops from two 1 bits to one.
  • Recounting every number from scratch, which passes but is a missed chance to show the reuse idea.
  • Using i / 2 in JavaScript without Math.floor or >> 1, so an odd i gives a fraction.
Questions an interviewer may ask next
  • Solve it in O(n) total time without a built in popcount function. (The first approach.)
  • Use the rule ones[i] = ones[i AND (i - 1)] + 1 instead. Why does it also work?
  • Find the largest count of 1 bits that any number up to n can have. (Think of the largest all-ones number that is at most n.)
  • Count the total number of 1 bits in all numbers from 0 to n without building the list. (Count each bit position separately.)