class Solution {
private:
  unordered_map<int, int> hashMap;

public:
  int toBits(int n) {
    if (hashMap.count(n)) {
      return hashMap[n];
    }

    int count = 0;

    while (n > 0) {
      if (hashMap.count(n)) {
        count += hashMap[n];
      } else if (n % 2 == 1) {
        count += 1;
      }

      n /= 2;
    }

    return hashMap[n] = count;
  }

  vector<int> countBits(int n) {
    vector<int> res(n + 1, 0);

    for (auto i = 0; i < res.size(); ++i) {
      res[i] = toBits(i);
    }

    return res;
  }
};