LeetCode Solutions
338. Counting Bits
Time: $O(n)$ Space: $O(n)$
class Solution {
public:
vector<int> countBits(int n) {
// Let f(i) := i's # of 1's in bitmask
// F(i) = f(i / 2) + i % 2
vector<int> ans(n + 1);
for (int i = 1; i <= n; ++i)
ans[i] = ans[i / 2] + (i & 1);
return ans;
}
};
class Solution {
public int[] countBits(int n) {
// Let f(i) := i's # of 1's in bitmask
// F(i) = f(i / 2) + i % 2
int[] ans = new int[n + 1];
for (int i = 1; i <= n; ++i)
ans[i] = ans[i / 2] + (i % 2 == 0 ? 0 : 1);
return ans;
}
}
class Solution:
def countBits(self, n: int) -> List[int]:
# Let f(i) := i's # Of 1's in bitmask
# F(i) = f(i / 2) + i % 2
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i // 2] + (i & 1)
return ans