x 338. Counting Bits

Counting Bits - LeetCodeLeetCode

2nd try - optimized

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function(n) {
    const ans = new Array(n + 1);
    ans[0] = 0;
    for (let i = 1; i <= n; i++) {
        ans[i] = ans[i >> 1] + (i & 1);
    }

    return ans;
};

1st try

time: O(N)

space: O(N)

/**
 * @param {number} n
 * @return {number[]}
 */

 /**
   ㅇ 관계식 내 항들 간의 관계 및 명칭은, 
     - 피제수 (dividend, 나눠지는 수) a 를, 
     - 제수 (divisor, 나누는 수 : Modulus, 모듈러스) m 로 나눌 때,
     - 몫 (quotient)을 q,
     - 나머지/잉여 (remainder, residue)를 r 이라고 함 
  */

const memo = {};

var countBits = function (n) {
    const ans = [];

    for (let i = 0; i <= n; i++) {
        const cnt = calc2(i);
        memo[i] = cnt;
        ans.push(cnt);
    }

    return ans;
};

function calc2(n, cnt = 0) {
    if (memo[n] !== undefined) {
        return memo[n] + cnt;
    }

    if (n === 0) {
        return cnt;
    }

    const q = Math.floor(n / 2);
    const mod = n % 2;
    cnt += mod;

    return calc2(q, cnt);
}