JS O(n) Solution


  • 1
    A
    /**
     * @param {number} num
     * @return {number[]}
     */
    var countBits = function(num) {
        var ret = [0];
        for(var i = 1; i <= num; i++){
            var c = i & i - 1;
            ret.push(ret[c] + 1);
        }
        return ret;
    };

  • 0
    R

    Excellent. I really want to know how could you find this solution. Could you tell me your train of thought?


  • 1
    A

    I found that countBit(n) = countBit(n & n-1) + 1, because we can use while(n){n &= n-1; cnt++} to calculate n's binary "1".


  • 0
    R

    Thank you very much. So as I think, you must be familiar with bitwise opreations. :)


Log in to reply
 

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