Counting Bits
- 2 min read
- LC-Easy
- Dynamic Programming
3 years ago
Solution
- What the fuck?
- Okay i'm looking at it the next day, it's very intuitive
- Starting from 0, we just add current number's remainder to same index in
dparray - And the remaining number, we do
dp[Math.floor(i / 2)]- Since we start from
i = 0, it is guaranteed that the value atdp[Math.floor(i / 2)]will have the correct value
- Since we start from
- Starting from 0, we just add current number's remainder to same index in
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
function countBits(n: number): number[] {
const dp = new Array(n + 1).fill(0);
for(let i = 1; i <= n; i++) {
dp[i] = (i % 2) + dp[Math.floor(i / 2)];
// dp[i] = dp[i >> 1] + (i & 1);
}
return dp;
};
Inefficient + Incorrect (?) Solution (DFS + Memoization)
I don't think the while loop (which divides cur by half each time) actually checks the memo object to see if we already pre-computed a value
function countBits(n: number): number[] {
const memo = {}
function dfs(i) {
if (i === 0) {
return 0;
}
if (Object.hasOwn(memo, i)) {
return memo[i];
}
let cur = i;
let ones = 0;
while (cur > 0) {
ones += cur % 2;
cur = Math.floor(cur / 2);
}
memo[i] = ones;
return ones;
}
for(let i = 0; i <= n; i++) {
memo[i] = dfs(i);
}
return Object.values(memo);
};