noodleProblems/
Counting Bits
#163

Counting Bits

AlgorithmeasyBit ManipulationDynamic Programming

Given a non-negative integer n, return an array ans of length n + 1 where ans[i] is the number of 1-bits (the Hamming weight) in the binary representation of i, for every i from 0 to n.

Example cases

  • n = 2
    in n = 2
    out [0,1,1]
    0 -> 0b0 (0 bits), 1 -> 0b1 (1 bit), 2 -> 0b10 (1 bit).
  • n = 5
    in n = 5
    out [0,1,1,2,1,2]
    3 -> 0b11 (2 bits), 4 -> 0b100 (1 bit), 5 -> 0b101 (2 bits).
  • n = 0
    in n = 0
    out [0]

Constraints

  • 0 <= n <= 10^5
Saved
n =
2