[−][src]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 } }