A interesting DP

  • 0

    We know that n & (n-1) will eliminate the first right "one", so the number of "one" of n minus the number of (n & (n-1)) is one.
    Than dp[i] = dp[i & (i-1)] + 1

    vector<int> countBits(int num) {
    vector<int> ret;
    for(int i = 1; i <= num; i++){
    ret.push_back((ret[(i-1) & i]) + 1);
    return ret;

Log in to reply

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