Counting Bits easy

Problem Statement

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 --> 0 1 --> 1 2 --> 10

Example 2:

Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101

Steps:

1. Initialization: Create an array ans of size n + 1 and initialize the first element ans[0] to 0 (since the binary representation of 0 has zero 1s).

2. Iteration: Iterate from i = 1 to n. For each i:

   • Calculate the number of 1s in the binary representation of i. We can do this efficiently using bit manipulation or by converting to a string.

3. Storing the count: Store the count of 1s in ans[i].

4. Return: Return the ans array.

Explanation:

The most straightforward approach involves iterating through each number from 0 to n, converting it to its binary representation, and counting the number of 1s. However, this can be inefficient for larger values of n. A more optimized approach leverages the observation that the number of 1s in a number's binary representation is closely related to the number of 1s in its preceding numbers.

Consider the pattern:

• 0: 0
• 1: 1
• 2: 1 (same as 1, but shifts to the left)
• 3: 2 (adds 1 to 1)
• 4: 1 (same as 1, but shifts left)
• 5: 2 (adds 1 to 1)
• 6: 2 (adds 1 to 1)
• 7: 3 (adds 1 to 2)
• 8: 1 (same as 1, but shifts left)

We notice that when a number is a power of 2 (1, 2, 4, 8, ...), the number of set bits resets to 1. Otherwise, the number of set bits is the number of set bits in the previous number plus one, or it is equal to the number of set bits in (number - nearest power of 2). The code below implements this optimization.

Code:

function countBits(n: number): number[] {
    const ans: number[] = new Array(n + 1).fill(0);
    let powerOf2 = 1; // Keep track of powers of 2
    let count = 1;   // Keep track of the number of 1s in the current power of 2

    for (let i = 1; i <= n; i++) {
        if (i === powerOf2) { // if it's a power of 2
            ans[i] = 1;      // count of 1s reset to 1
            powerOf2 *= 2;   // update power of 2
            count = 1;
        } else {
            ans[i] = ans[i - count] + 1; //Add 1 to the count of 1s in the previous number - nearest power of 2
        }

    }
    return ans;
};

Complexity:

• Time Complexity: O(n). We iterate through the numbers from 1 to n once.
• Space Complexity: O(n). We use an array of size n+1 to store the results.