C++ DP solution with explanation


  • 0
    D

    when we count the bits of i, let's check the last bit of i-1
    if the last bit of i-1 is 1, the bits of i must be count[i - 1] + 1
    if the last bit of i-1 is 0, i is i-1 plus 0x01, the last bit of i would be 0,
    but a carry 1 would be added to the former bits except the last one,
    so the number of bit i must be count[(i >> 1) + 1]

    vector<int> countBits(int num) {
        vector<int> count(num + 1, 0);
        for (int i = 1; i <= num; ++i) {
            int pre = i - 1;
            if (pre & 0x01) {
                count[i] = count[(pre >> 1) + 1];
            } else {
                count[i] = count[pre] + 1;
            }
        }
        return count;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.