text: // 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 <= 105
   
  // Follow up:
  
  // It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
  // Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?
  
  // O(n log n)
  class Solution {
  public:
      vector<int> ans;
      int countSetBits(int n)
      {
          int count = 0;
          while(n)
          {
              int a = (n&1);
              if(a) count++;
              n = n>>1;
          }
          return count;
      }
      vector<int> countBits(int num) {
          for(int i=0;i<=num;i++)
          {
              int s = countSetBits(i);
              ans.push_back(s);
          }
          return ans;
      }
  };
  
  // O(n)
  
  class Solution {
  public:
      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;
      }
  };
  
  