Counting bits

Dynamic Programming Bit Manipulation

80.4% acceptance

Jan 12, 2026

11916

611

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_bits(n: i32) -> Vec<i32> {
    let n = n as usize;
    let mut result = vec![0; n + 1];
    
    for i in 1..=n {
      result[i] = result[i >> 1] + (i & 1) as i32;
    }
    
    result
  }
}