338. Counting Bits Easy

1/**
2 * [338] Counting Bits
3 *
4 * 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.
5 *  
6 * Example 1:
7 * 
8 * Input: n = 2
9 * Output: [0,1,1]
10 * Explanation:
11 * 0 --> 0
12 * 1 --> 1
13 * 2 --> 10
14 * 
15 * Example 2:
16 * 
17 * Input: n = 5
18 * Output: [0,1,1,2,1,2]
19 * Explanation:
20 * 0 --> 0
21 * 1 --> 1
22 * 2 --> 10
23 * 3 --> 11
24 * 4 --> 100
25 * 5 --> 101
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	0 <= n <= 10^5
31 * 
32 *  
33 * Follow up:
34 * 
35 * 	It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
36 * 	Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/counting-bits/
42// discuss: https://leetcode.com/problems/counting-bits/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn count_bits(n: i32) -> Vec<i32> {
48        vec![]
49    }
50}
51
52// submission codes end
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_338() {
60    }
61}
62