Counting Bits

Translated from German using DeepL.

Date: May 2025
Reading time: 4 minutes

Derivation and solution of the Leetcode Challenge.

Nr.: 338
Difficulty: Easy
Link: https://leetcode.com/problems/counting-bits (opens in a new tab)

Problem

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Example 1

Input: n = 2
Output: [0,1,1]
Explanation:

0 --> 00
1 --> 01
2 --> 10

Example 2

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:

0 --> 000
1 --> 001
2 --> 010
3 --> 011
4 --> 100
5 --> 101

Constraints

0 <= n <= 105

Solution

Derivation

Binary numbers are made up as follows:

✅ 1 (activ; highestBit - is explained below)
🟩 1 (activ)
🟥 0 (inactive)

The result of each number is to be stored and returned in an array ans. This array is initialized with the value 0 at the beginning, as the number 0 has no 1 in its binary representation and therefore serves as the initial value.

/**
 * @param {number} n
 * @return {number[]}
 */
function countBits(n) {
    let ans = [0];
    return ans;
}

A loop can later be used to perform the calculation for the desired number of numbers.

/**
 * @param {number} n
 * @return {number[]}
 */
function countBits(n) {
    let ans = [0];
    for (let i = 1; i <= n; i++) {}
    return ans;
}

The number of activated bits must be determined for all subsequent numbers. It is known that each number has at least one active bit. In addition, it can be determined that previous calculation results can be reused if there is more than one active bit.

For example, the results of the numbers 2 and 1 can be used to calculate the number of bits of 3.

To do this, the first/highest bit must be identified. For this, determine the largest exponent of 2 that can still represent the number. This exponent is referred to here as the highestBit. In the tables, this is marked with a ✅.

This is what this value looks like:

The highestBit variable can be used to determine the largest active bit.
The variable is initialized with 1. As soon as an exponent of 2 (2, 4, 8, ...) is reached, the value of the variable is adjusted accordingly.

/**
 * @param {number} n
 * @return {number[]}
 */
function countBits(n) {
    let ans = [0];
    let highestBit = 1;
 
    for (let i = 1; i <= n; i++) {
        if (highestBit * 2 === i) highestBit *= 2;
    }
 
    return ans;
}

Part of the number is already covered by the highestBit. The remaining/lower bits still need to be determined. Example: The number 7 has its highestBit at 4. To determine the remaining active bits, the value 3 (7 - 4) is evaluated.

✅ 1 (activ; highestBit)
🟩 1 (activ)
🟥 0 (inactiv)

However, the number of active bits contained in 3 does not need to be recalculated. It is already known at this point and can be read out directly.

✅ 1 (activ; highestBit)
🟩 1 (activ)
🟥 0 (inactiv)

Formula

The result is the sum of 1 for the set highest bit and the already known result for the remaining value. This results in the following formula:

ans[i] = 1 + ans[i - highestBit];

Example:

ans[7] = 1 + ans[7 - 4];

ans[7] = 1 + ans[3];

0: 0
1: 1
2: 1
3: 2 <- ans[3]
4: 1
5: 2
6: 2
7: 1 + ans[3]

ans[7] = 1 + 2;

Code

/**
 * @param {number} n
 * @return {number[]}
 */
function countBits(n) {
    let ans = [0];
    let highestBit = 1;
 
    for (let i = 1; i <= n; i++) {
        if (highestBit * 2 === i) highestBit *= 2;
        ans[i] = 1 + ans[i - highestBit];
    }
 
    return ans;
}

Process visualized

countBits(7);

✅ 1 (activ; highestBit)
🟩 1 (activ)
🟥 0 (inactiv)

* i - highestBit
** ans[i - highestBit]
*** 1 + ans[i - highestBit]