// My own solution
class Solution {public:    vector<int> countBits(int num) {        vector<int> ret = {0};        if(num <= 0) return ret;        ret.push_back(1);        int i = 2;        while(i <= num){           int start = (i >> 1) - 1;           int mid = i;           int end = mid << 1;           while(++start < mid && i <= num){               ret.push_back(ret[start]);               i++;           }           mid -= 1;           while(i < end && i <= num){               ret.push_back(ret[++mid] + 1);               i++;           }        }        return ret;    }};

// Others‘ solution
class Solution {public:    vector<int> countBits(int num) {        vector<int> ret(num + 1, 0);        for(int i = 1; i <= num; i++){              ret[i]=ret[i / 2]+(i % 2);          }        return ret;    }};