C++ One pass solution, based on even/odd, no library function call


  • 0
    A

    15 / 15 test cases passed
    Status: Accepted
    Runtime: 59 ms

    class Solution {
    public:
        vector<int> countBits(int num) {
            // Count of 1's in i:
            // Odd:  i = (i-1) | 1, previous count + 1
            // Even: i = i/2 << 1, same count as i/2
            vector<int> v(num+1);
            for (uint i = 0; i <= num; i++) {
                if (i & 1) v[i] = v[i-1] + 1;
                else v[i] = v [i / 2];
            }
            return v;
        }
    };
    

Log in to reply
 

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