Counting Bits - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const DONE = 'done', DONE_COLOR = 'green';
const CURRENT_NUM = 'current_num', CURRENT_NUM_COLOR = 'blue';
const SHIFTED_NUM = 'shifted_num', SHIFTED_NUM_COLOR = 'orange';

function visMainFunction(n) {
    initClassProperties();

    startBatch();
    const onesCount = new VisArray(n + 1);
    onesCount[0] = 0;
    onesCount.makeVisManagerForIndex(0).addClass(DONE);
    endBatch();

    explanationAndColorSchemaNotifications();

    for (let currentNum = 1; currentNum <= n; currentNum++) {
        startPartialBatch();
        const numVm = onesCount.makeVisManagerForIndex(currentNum).addClass(CURRENT_NUM);

        const shiftedNum = currentNum >> 1;
        const lastBit = currentNum & 1;

        explainComputationStep(onesCount, currentNum, shiftedNum, lastBit);

        onesCount[currentNum] = onesCount[shiftedNum] + lastBit;

        numVm.removeClass(CURRENT_NUM).addClass(DONE);
        endBatch();
    }

    notification(`🏁 <b>Completed!</b> The final result is stored in <code>onesCount</code>. ✅`);
    return onesCount;
}

function explainComputationStep(onesCount, currentNum, shiftedNum, lastBit) {
    const shiftedNumVm = onesCount.makeVisManagerForIndex(shiftedNum).addClass(SHIFTED_NUM);

    notification(`
        🔄 <b>Calculating the number of 1’s in 
        ${makeColoredSpan(`currentNum (${currentNum}) (in binary: ${currentNum.toString(2)})`, CURRENT_NUM_COLOR)}</b>, and storing the result in 
        <code>onesCount[${makeColoredSpan(`currentNum (${currentNum})`, CURRENT_NUM_COLOR)}]</code>:
        <ul>

            <li>
                Binary prefix without the last bit is
                ${makeColoredSpan('shiftedNum', SHIFTED_NUM_COLOR)} = ${makeColoredSpan('currentNum', CURRENT_NUM_COLOR)} >> 1 = 
                <b>${makeColoredSpan(`${shiftedNum} (in binary: ${shiftedNum.toString(2)})`, SHIFTED_NUM_COLOR)}</b>
            </li>

            <li>
                Last bit of <code>currentNum</code> (<code>currentNum &amp; 1</code>) is <b>${lastBit}</b>
            </li>

            <li>
                The number of 1’s in 
                ${makeColoredSpan(`currentNum (${currentNum})`, CURRENT_NUM_COLOR)}
                is equal to:
                <br>
                <b>• the number of 1’s in the prefix (stored in 
                onesCount[
                    ${makeColoredSpan(`shiftedNum (${shiftedNum})`, SHIFTED_NUM_COLOR)}
                ])</b>
                <br>
                <b>• plus the last bit (${lastBit})</b>
                <br><br>
                Therefore:
                <br>
                <code>
                    onesCount[${makeColoredSpan(`currentNum (${currentNum})`, CURRENT_NUM_COLOR)}] = 
                    onesCount[${makeColoredSpan(`shiftedNum (${shiftedNum})`, SHIFTED_NUM_COLOR)}] (${onesCount[shiftedNum]}) + ${lastBit}
                    = <b>${onesCount[shiftedNum] + lastBit}</b>
                </code>
            </li>

        </ul>
    `);

    shiftedNumVm.removeClass(SHIFTED_NUM);
}

function initClassProperties() {
    setClassProperties(DONE, { backgroundColor: DONE_COLOR });
    setClassProperties(CURRENT_NUM, { borderColor: CURRENT_NUM_COLOR });
    setClassProperties(SHIFTED_NUM, { borderColor: SHIFTED_NUM_COLOR });
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        <b>🎨 Visual Cues (Color Schema)</b>
        <ul>
            <li>
            ${makeColoredSpan('Computed entry', DONE_COLOR)} — 
            highlighted with a <b>${DONE_COLOR} background</b> to mark cells in 
            <code>onesCount</code> whose values are already finalized.
            </li>

            <li>
            ${makeColoredSpan('Current number', CURRENT_NUM_COLOR)} — 
            highlighted with a <b>${CURRENT_NUM_COLOR} border</b> to show 
            the index <code>currentNum</code> whose count of 1’s is being computed.
            </li>

            <li>
            ${makeColoredSpan('Shifted number', SHIFTED_NUM_COLOR)} — 
            highlighted with a <b>${SHIFTED_NUM_COLOR} border</b> to show 
            the index <code>shiftedNum = currentNum >> 1</code> whose value is reused 
            in the DP formula.
            </li>
        </ul>
    `);
}

Approach

We want to compute, for every integer i in the range [0, n], the number of 1 bits (set bits) in the binary representation of i. We store each result in an array onesCount where onesCount[i] = “number of 1’s in the binary representation of i”.
Key idea — reuse work by removing the last bit:
For any integer currentNum, its binary form can be split into:

(binary prefix) · (last bit)

The number of 1’s in the binary representation of currentNum equals the number of 1’s in the binary prefix plus the value of the last bit. Since we fill onesCount in increasing order, the count of 1’s in the binary prefix must already be stored in the DP array. The index for this prefix is the decimal value of the prefix itself, which we call shiftedNum, computed as currentNum >> 1. The last bit (denoted lastBit) is obtained using currentNum & 1. Therefore, the count of 1’s in currentNum is simply:

onesCount[currentNum] = onesCount[shiftedNum] + lastBit.
Dynamic programming relation:
We build onesCount in increasing order so that onesCount[shiftedNum] is always known before computing onesCount[currentNum].
- shiftedNum = currentNum >> 1
- lastBit = currentNum & 1
- onesCount[currentNum] = onesCount[shiftedNum] + lastBit
Building the table:
- Initialize onesCount with n + 1 entries.
- Set onesCount[0] = 0.
- For each currentNum from 1 to n, apply the formula above.

Time Complexity

We iterate once from 1 to n, and each step performs only constant-time operations using the dynamic programming relation. Therefore, the overall time complexity of the algorithm is O(n).

Space Complexity

O(n) — We store one computed value for each integer from 0 to n in the output array.

Input-1

Counting Bits - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity