·

# Problem statement

Given an integer `n`, return an array `ans` of length `n + 1` such that for each `i` (`0 <= i <= n`), `ans[i]` is the number of `1`'s in the binary representation of `i`.

## Example 1

``````Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
``````

## Example 2

``````Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
``````

## Constraints

• `0 <= n <= 10^5`.

# Solution 1: Count the binary representation using `std::bitset`

## Code

``````#include <vector>
#include <iostream>
#include <bitset>
using namespace std;
vector<int> countBits(int n) {
vector<int> ans;
for (int i = 0; i <= n; i++) {
bitset<17> b(i); // 17 bits to make sure it can exceed 10^5
ans.push_back(b.count());
}
return ans;
}
void print(vector<int>& ans) {
cout << "[";
for (int a : ans) {
cout << a << ",";
}
cout << "]\n";
}
int main() {
auto ans = countBits(2);
print(ans);
ans = countBits(5);
print(ans);
}
``````
``````Output:
[0,1,1,]
[0,1,1,2,1,2,]
``````

## Complexity

• Runtime: `O(nlogn)`.
• Extra space: `O(1)`.

# Solution 2: Finding the pattern

1. If you append a bit `0` to the binary representation of an integer `i`, you perform the operator `i -> 2*i` but the number of bits `1` is unchanged. In other words, `ans[2*i] = ans[i]`.
2. If you append a bit `1` to the binary representation of `i`, you perform the operator `i -> 2*i + 1` and the number of bits `1` is incremented one. In other words, `ans[2*i + 1] = ans[i] + 1`.

## Code

``````#include <vector>
#include <iostream>
using namespace std;
vector<int> countBits(int n) {
vector<int> ans(n + 1);
ans[0] = 0;
for (int i = 1; i <= n; i++) {
ans[i] = ans[i/2] + (i % 2);
}
return ans;
}
void print(vector<int>& ans) {
cout << "[";
for (int a : ans) {
cout << a << ",";
}
cout << "]\n";
}
int main() {
auto ans = countBits(2);
print(ans);
ans = countBits(5);
print(ans);
}
``````
``````Output:
[0,1,1,]
[0,1,1,2,1,2,]
``````

## Complexity

• Runtime: `O(n)`.
• Extra space: `O(1)`.