codekofi
← All questions

Counting Bits

HardBit Manipulation

The problem

For every number from 0 up to n, count the set bits in its binary form.

Return the counts in order, so the result has n + 1 entries.

countBits(5)

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1vector<int> countBits(int n) {
2
3 vector<int> ans(n, 0);
4
5 for (int i = 1; i < n; i++) {
6 ans[i] = ans[i >> 1] + (i & 1);
7 }
8
9 return ans;
10}
1vector<int> countBits(int n) {
2
3 vector<int> ans(n, 0);
4
5 for (int i = 1; i <= n; i++) {
6 ans[i - 1] = ans[i >> 1] + (i & 1);
7 }
8
9 return ans;
10}
1vector<int> countBits(int n) {
2
3 vector<int> ans(n + 1, 0);
4
5 for (int i = 1; i <= n; i++) {
6 ans[i] = ans[i >> 1] + (i & 1);
7 }
8
9 return ans;
10}