Function leetcode_for_rust::cd0338_counting_bits::count_bits

pub fn count_bits(num: i32) -> Vec<i32>

Solutions

Approach 1: Iteration

• Time complexity: O(n)

• Space complexity: O(1)

• Runtime: 4 ms

• Memory: 2.9 MB

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

Approach 2: Iteration

• Time complexity: O(n)

• Space complexity: O(1)

• Runtime: 12 ms

• Memory: 2.9 MB

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