O(N) solution with amortized analysis


  • 0
    P
    class Solution {
    public:
        vector<int> countBits(int num) {
            int n{0}, one{0};
            vector<int> res{0};
            for (int i = 1; i <= num; ++ i) {
                int y{1};
                for (int j = 0; y ; ++ j) {
                    if ((n >> j) & 1) {
                        -- one, n ^= 1 << j;
                    } else {
                        n ^= 1 << j, ++ one;
                        y = 0;
                    }
                }
                res.push_back(one);
            }
            return res;
        }
    };
    

Log in to reply
 

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