leetcode_for_rust/cd0338_counting_bits/
mod.rs

1//! Counting Bits [counting_bits](https://leetcode.com/problems/counting-bits/)
2//!
3//! Given a non negative integer number **num**. For every numbers i in the range **0 ≤ i ≤ num** calculate the number of 1's in their binary representation and return them as an array.
4//!
5//! ***Example1:***
6//!
7//! ```
8//! Input: 2
9//! Output: [0,1,1]
10//! ```
11//!
12//! ***Example2:***
13//!
14//! ```
15//! Input: 5
16//! Output: [0,1,1,2,1,2]
17//! ```
18//!
19//! **Follow up::**
20//!
21//! * It is very easy to come up with a solution with run time **O(n*sizeof(integer))**. But can you do it in linear time **O(n)** /possibly in a single pass?
22//! * Space complexity should be **O(n)**.
23//! * Can you do it like a boss? Do it without using any builtin function like **__builtin_popcount** in c++ or in any other language.
24
25/// # Solutions
26///
27/// # Approach 1: Iteration
28///
29/// * Time complexity: O(n)
30///
31/// * Space complexity: O(1)
32///
33/// * Runtime: 4 ms
34/// * Memory: 2.9 MB
35///
36/// ```rust
37/// impl Solution {
38///     pub fn count_bits(num: i32) -> Vec<i32> {
39///         let mut bits = vec![0; (num + 1) as usize];
40///         for i in 1..=num as usize {
41///             bits[i] = bits[i & (i - 1)] + 1;
42///         }
43///         bits
44///     }
45/// }
46/// ```
47///
48/// # Approach 2: Iteration
49///
50/// * Time complexity: O(n)
51///
52/// * Space complexity: O(1)
53///
54/// * Runtime: 12 ms
55/// * Memory: 2.9 MB
56///
57/// ```rust
58/// impl Solution {
59///     pub fn count_bits(num: i32) -> Vec<i32> {
60///         let mut result = vec![];
61///         for i in 0..=num {
62///             let mut j = i;
63///             let mut count = 0;
64///             while j != 0 {
65///                 count += 1;
66///                 j &= (j - 1);
67///             }
68///             result.push(count);
69///         }
70///         result
71///     }
72/// }
73/// ```
74///
75pub fn count_bits(num: i32) -> Vec<i32> {
76    let mut bits = vec![0; (num + 1) as usize];
77    for i in 1..=num as usize {
78        bits[i] = bits[i & (i - 1)] + 1;
79    }
80    bits
81}
leetcode_for_rust/cd0338_counting_bits/mod.rs

leetcode_for_rust/cd0338_counting_bits/
mod.rs
