Another from the archives! I had a lot of fun with this one. Would others? I don’t know! We can use a sort-of dynamic programming approach (maybe this is a good replacement for that frustrating “Fib” standard warmup?) to avoid calling popcount over and over again. Not sure what’s actually faster on hardware, but I like the principle here.

This is a good algorithmic-thinking question, I think. Requires some fluency with bit manipulation, though.

class Solution {
public:
    vector<int> countBits(int num) {
        if (num == 0) { return {0}; }
        if (num == 1) { return {0, 1}; }
        if (num == 2) { return {0, 1, 1}; }
        vector<int> res(num+1);
        res[0] = 0;
        res[1] = 1;
        for (int i = 2; i <= num; ++i) {
            const int lastBit = i % 2;
            res[i] = res[i/2] + lastBit;
        }
        return res;
    }
};

Notes

Additional implementation details? I don’t know. I found it reassuring that the length of the output is required to be num, because there’s always that potential psuedopolynomial trap. Fixing the output size (versus, say, we’d have to return the total numbers of 1s or something) helps make it unambiguous that we’d at least be able to iterate through all inputs.

Other bit-manipulating questions are collected here. Other dynamic-programming questions are collected here.