c++ 3 different DP solutions, 5-6 lines


  • 0
    vector<int> countBits(int num) {
            vector<int> cnt(num + 1, 0);
            
            for (int i = 1; i <= num; i++) {
                cnt[i] = cnt[i & (i - 1)] + 1;      // i & (i - 1) is i without lowest 1 bit
            }
            
            return cnt;
    }
    
    vector<int> countBits(int num) {
            vector<int> cnt(num + 1, 0);
            
            for (int i = 1, k = 0, bound = 1; i <= num; i++) {
                cnt[i] = cnt[k] + 1;                            // k is i without highest 1 bit
                if (++k == bound) { k = 0, bound <<= 1; }       // update k
            }
            
            return cnt;
    }
    
    vector<int> countBits(int num) {
            vector<int> cnt (num + 1, 0);
            
            for (int i = 1; i <= num; i++) {
                cnt[i] = cnt[i >> 1] + (i & 1);         // isolate i's lowest bit
            }
            
            return cnt;
    }
    

  • 0
    D

    Great solutions. Thanks for sharing.


Log in to reply
 

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