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.


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.


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.


class Solution {

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