Counting Bits

easy

Return array where ans[i] is the number of 1s in binary of i

Counting Bits

Key Insight

bits[i] = bits[i >> 1] + (i & 1). Use previously computed values.

Step 1Base Case
0
0
=
0
0
0
0
0
0
0
0
76543210
bits[0] = 0

bits[0] = 0 (no 1-bits in 0)

1 / 5

Learn the Pattern

Bit ManipulationUse bitwise operations to solve problems efficiently by treating integers as arrays of bits.
Practice the Code

Step-by-Step Walkthrough: Counting Bits

bits[i] = bits[i >> 1] + (i & 1). Use previously computed values.

  1. Base Case

    bits[0] = 0 (no 1-bits in 0)

  2. Formula

    bits[i] = bits[i/2] + (i mod 2)

  3. Example: i=5

    5>>1=2, 5&1=1. bits[5] = bits[2] + 1 = 1+1 = 2

  4. Build Array

    For n=5: [0,1,1,2,1,2]

  5. Result

    O(n) solution using DP!