338. Counting Bits

My intuition is to count bits for each number. So the total run time is O(32*n). However, if we look at binary representation closely,  "0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111", we'll see that once we reach a multiple of 2 say 2^n, its right bits just repeat all the numbers from 0 to 2^n-1. So we can program dynamically.

1:  class Solution {  
2:  public:  
3:    vector<int> countBits(int num) {  
4:      int shift = 0;  
5:      vector<int> res(num+1, 0);  
6:      int i = 1, j = 0;  
7:      while (i <= num) {  
8:        for (int j = 0; i <= num && j <(1<<shift); i++,j++) {  
9:          res[i] = res[j]+1;  
10:        }  
11:        shift++;  
12:      }  
13:      return res;  
14:    }  
15:  };