:orphan:

Counting Bits
=============

.. highlight:: none

Problem
-------
https://leetcode.com/problems/counting-bits/

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``.



**Example 1:**

::

   Input: n = 2
   Output: [0,1,1]
   Explanation:
   0 --> 0
   1 --> 1
   2 --> 10

**Example 2:**

::

   Input: n = 5
   Output: [0,1,1,2,1,2]
   Explanation:
   0 --> 0
   1 --> 1
   2 --> 10
   3 --> 11
   4 --> 100
   5 --> 101



**Constraints:**

- ``0 <= n <= 10``\ :sup:`5`

.. highlight:: python

Pattern
-------
Bit Manipulation, Dynamic Programming

Approaches
----------

.. tab-set::

    .. tab-item:: Bit Counting

        **Code**

        .. literalinclude:: ../problems/medium/counting-bits/counting_bits__bit_counting.py
            :language: python
            :lines: 12-

        **Test**

        >>> from counting_bits__bit_counting import countBits
        >>> countBits(2)
        [0, 1, 1]
        >>> countBits(5)
        [0, 1, 1, 2, 1, 2]
        >>> countBits(0)
        [0]

        .. autofunction:: counting_bits__bit_counting.countBits

    .. tab-item:: DP

        **Code**

        .. literalinclude:: ../problems/medium/counting-bits/counting_bits__dp.py
            :language: python
            :lines: 12-

        **Test**

        >>> from counting_bits__dp import countBits
        >>> countBits(2)
        [0, 1, 1]
        >>> countBits(5)
        [0, 1, 1, 2, 1, 2]
        >>> countBits(0)
        [0]

        .. autofunction:: counting_bits__dp.countBits