Four lines, C++, time O(n), space O(n)


  • 147
    F
    class Solution {
    public:
        vector<int> countBits(int num) {
            vector<int> ret(num+1, 0);
            for (int i = 1; i <= num; ++i)
                ret[i] = ret[i&(i-1)] + 1;
            return ret;
        }
    };

  • -17
    A

    Won't i&(i-1) take sizeof(integer) time?


  • 0
    R

    It's O(n) space. You can't solve it O(1) space as you are returning an array of size num.


  • 0
    X

    Yes. It's O(n) space. The title is wrong.


  • 0
    X

    It's a constant time operation.


  • 0
    F

    Yes, it was my fault and I have made it right. Thanks !


  • 0
    L

    Can you explain a bit why i&(i-1)?


  • 48
    F

    i&(i-1) drops the lowest set bit. For example: i = 14, its binary representation is 1110, so i-1 is 1101, i&(i-1) = 1100, the number of "1" in its binary representation decrease one, so ret[i] = ret[i&(i-1)] + 1. (Sorry, my English is so poor and I have tried my best to make it clearly, I hope you can understand my explanation)


  • 1
    L

    Thanks fengcc, it is very clear!


  • 1
    I

    This answer bothers me. How would you begin to figure out this method? iterating through and bit shifting is easy to see, but I couldn't see myself coming up with this method without significant prodding.


  • 0
    P

    @fengcc you are so clever!!!!! the idea is so beautiful


  • 11
    B

    Just want to add to fengcc's explanation, as it still took me sometime to think it through. So when you remove the lowest set bit (or the rightmost non-zero bit), you will arrive at a smaller number than the current number: 14 ==> 12. Since your computed series already includes all the counts for n=0,1,2,...,12,13, you will most certainly already have the count for the number 12. And as fengcc pointed out, the only difference in count between 14, and 12 is 1 bit, so you add 1 to the count for 12 and get the correct count for 14.


  • 0
    M

    How elegant to rely directly on the nature of the question. Doesn't even need to derive a pattern.


  • 0
    K

    Nice...
    How beautiful code it is.


  • 0

    @fengcc Nice solution! I never thought about the iteration to solve the problem with for;


  • 0
    D

    it's very great! after read @fengcc explanation and think it through ,I write it for myself :
    It is need to return an array, which every item value is the numbers '1' in binary of the item's sequence No. . As i&(i-1) decrease one '1', so array[i] - 1= array[i&(i-1)] , then array[i] = array[i&(i-1)] + 1.


  • 0
    M

    yeah , the code is very easy to understand , however I can't come up with such idea to solve this question , can you
    tell me how do you improve your thinking in daily life


  • 1
    J

    lihailewodege


  • 0
    A

    I think the logic is great, but how can you prove that bit_count(i & i-1) will be always bit_count(i)-1? Is it known formula?


  • 2
    M

    @asbear yeah, same question here, the code is definitely elegant, but I don't know why it works.


Log in to reply
 

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