/**
* @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);
}