My own Answer: [C++] A single pass. Time Complexity O(n)


  • 1
    L

    Method 1: // remove the highest bit

    class Solution {
    public:
    vector<int> countBits(int num) {
        vector<int> A(num+1, 0);
        int flag = 0;
        for (int i = 1; i <= num; ++i) {  
            if (i & (i-1)) {
                A[i] = A[i-flag] + 1;
            } else {
                A[i] = 1;
                flag = i;
            }
        }
        return A;
    }
    };
    

    Think: 1. make 1, 2, 4, 8, 16 as speciatial points which record the highest bit.

    Think: 2 . A num remove its highest bit get a new num as V, which is alread known. return A[V] +1 is OK.

    Method 2

     A[i] = A[i >> 1] + (i & 1); // remove the lowest bit.

Log in to reply
 

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