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 <= 105

    Follow up:

    • 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?
    • Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

    Runtime: 92 ms, faster than 95.57% of JavaScript online submissions for Counting Bits.
    Memory Usage: 44.9 MB, less than 48.86% of JavaScript online submissions for Counting Bits.

    1. /**
    2.  * @param {number} n
    3.  * @return {number[]}
    4.  */
    5. var countBits = function(n) {
    6.     const result = [0];
    7.     let half;
    8.     for (let i = 1; i <= n; i++) {
    9.         half = Math.floor(i / 2);
    10.         result[i] = result[half] + i % 2;
    11.     }
    13.     return result;
    14. };