###### tags: `leetcode`
# LeetCode #338 Counting Bits - Solution by CharlieHe
> ref = https://leetcode.com/problems/counting-bits/discuss/332666/100-ms-faster-than-99.06-memory-Usage-less-than-97.01-of-Python3
## CharlieHe's

class Solution:
    def countBits(self, num: int) -> List[int]:
        _num = num
        res = [0]
        while _num >= 1:
            res += list(map(lambda x: x+1, res))
            _num //= 2
        return res[:num+1]

### `list()`, eating iterator, returning list

> ref = https://www.programiz.com/python-programming/methods/built-in/list

* Create list from sequence: string, tuple and list.
* Create list from collection: set and dictionary
* Create list from custom iterator object

### a list `+` another list
Append one list to another.

[0, 1, 2, 3, 4] + [5, 6, 7, 8, 9]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

### `map()`, returning iterator

> ref = http://www.runoob.com/python/python-func-map.html

>> Note that map() in Python2 returns a list

A `map()` takes a function and iterable sequence.

an_iterator = map(function, iterable_sequence_0, iterable_sequence_1, ...) 

A `map()` returns an *iterator* (a kind of *generator*), in Python3.

in [1]: map(lambda x: x ** 2, [1, 2, 3, 4, 5])
Out[1]: <map at 0x7f3b01850c18>

#### *Iterator* in Python 3

> ref = http://zetcode.com/lang/python/itergener/

In this part of the Python tutorial, we work with interators and generators. Iterator is an object which allows a programmer to traverse through all the elements of a collection, regardless of its specific implementation.

In Python, an iterator is an object which implements the iterator protocol. The iterator protocol consists of two methods. The __iter__() method, which must return the iterator object, and the next() method, which returns the next element from a sequence.

Iterators have several advantages:

- Cleaner code
- Iterators can work with infinite sequences
- Iterators save resources

## york's thinking

I approach is:
- find the next $2^p-1$
- do the doubling $p$ times
- take the first $n$ elements

The next $2^p-1$ is the lg(floor())

I was thinking to find $2^p-1$ by $2^p-1 = 2^{floor[lg(n+1)]}-1$

Since Python doesn't have a build-in log(), I was thinking about to find $2^p-1 = 2^{floor[lg(n+1)]}-1$ by bitwise operation.

But CharlieHe