Problem

Problem ID: 338

Title: Counting Bits

Difficulty: Easy

Description: 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.

Thoughts

Even though this question is LC easy question, I was not able to derive the most optimal solution without looking at the solution. Admittedly, I was intellectually lazy to push myself to think of the most optimal solution and went with the naive solution of counting the number of bits for each number using while(num > 0){num = num & (num-1);} method.

Solution

The number of set bit for i is either equal to the number of set bit of i/2 if i is even else it is 1 more than the number of set bit of i-1. With this information we can easily derive the following dp solution.

Implementation

class Solution {
public:

vector<int> countBits(int n) {
vector<int>ans;
ans.push_back(0);

for (int i = 1; i <= n; i++) {
if (i&1) {
ans.push_back(ans[i-1] + 1);
} else {
ans.push_back(ans[i/2]);
}
}
return ans;
}
};