Thought process & DP solution in JS


  • 0
    K

    My thought process:

    First I wrote down the binary representation of the first few integers

    [0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010]
    
    

    then I circled the numbers that are a power of 2 (10, 100, 1000, ...).
    After that, I noticed that all other numbers can be expressed as the sum of (power of 2 smaller than itself + some integer smaller than itself).

    For example number 9 = (8 + 1)
    The number of 1 bit for 9 corresponds to (number of bit for 8 + number of bit for 1).
    If the number is a power of 2, then the number of 1 bit is one (the most significant bit).
    With this, we can use a bottom-up approach to generate the array.
    I implemented this with JS.

    /**
     * @param {number} num
     * @return {number[]}
     */
    const countBits = (num) => {
        const bits = [0];
        for (let i = 1; i <= num; i++) {
            const exp = Math.floor(Math.log2(i));
            const pow = Math.pow(2, exp);
            const other = i - pow;
            if (other === 0) {
                bits.push(1);
            } else {
                const bitCount = 1 + bits[other];
                bits.push(bitCount);
            }
        }
        return bits;
    };
    

  • 0
    G

    @kenhibino this was really helpful, thanks!


Log in to reply
 

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