Shortest c++ solution with simple explaination


  • 1
    5

    if A / 2 = B, that means A has one bit more than B, and A has same characters with B except the right most one.

    for example A = 11 and B = 5, we can see A = 1011, and B = 101, the leftmost three characters of A is same with B, so the numbers of 1s of A is decided by B and the rightmost character of A, if the rightmost character is 1, then A has one more 1 than B, else they have same number of 1.

    class Solution {
    public:
        vector<int> countBits(int num) {
            vector<int> vec(num+1, 0);
            for(int i =1; i <= num; i++)
                vec[i] = vec[i/2] + i%2;   
            return vec;
        }
    };

Log in to reply
 

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