Counting Bits | Engineering Interview Kit

Concept

LeetCode #338.
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.

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

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

The Brute Force Approach ( $O(N \log N)$ )

We could just run a for loop from 0 to n. Inside the loop, we call the Brian Kernighan function hammingWeight(i) we wrote in the previous section.
Because hammingWeight takes $O(\log N)$ time (it loops based on the number of bits), doing it $N$ times results in an $O(N \log N)$ time complexity.

This is acceptable, but the interviewer will ask: “Can you do it in $O(N)$ time using Dynamic Programming?”

The Dynamic Programming Strategy ( $O(N)$ )

Dynamic Programming remembers the past. If we want to know how many 1s are in the number 5 (101), do we really need to count them all from scratch?

Look at the binary for 5: 101.
If we chop off the last bit, what number is left? 10 (which is 2 in binary).
Did we already calculate how many 1s are in the number 2 earlier in the array? Yes! ans[2] is 1.
So, the number of 1s in 5 is exactly equal to the number of 1s in 2, PLUS whatever that chopped-off bit was! The chopped-off bit is 1, so 1 + 1 = 2. The answer is 2!

The Recurrence Relation:
How do we chop off the last bit of a number i? We right shift it! i >> 1.
How do we check what that chopped off bit was? We AND it with 1! i & 1.
dp[i] = dp[i >> 1] + (i & 1)

Implementation

// Time Complexity: O(N) (Exactly one pass through the array)
// Space Complexity: O(N) (To store the result array)

function countBits(n: number): number[] {
    const dp = new Array(n + 1).fill(0);
    
    // Base Case: 0 has zero 1s.
    dp[0] = 0;

    for (let i = 1; i <= n; i++) {
        // The number of 1s in my prefix (i >> 1), 
        // PLUS my own final bit (i & 1).
        dp[i] = dp[i >> 1] + (i & 1);
    }

    return dp;
}

The “Even/Odd” Alternative Logic

There is a slightly different way to conceptualize the exact same DP approach.

If a number is Even: (e.g., 4 100).
An even number in binary ALWAYS ends in 0. Therefore, it has the exact same number of 1s as its half!
4 (100) has the exact same number of 1s as 2 (010).
If i is Even: dp[i] = dp[i / 2]

If a number is Odd: (e.g., 5 101).
An odd number is literally just the even number before it, but with the final 0 flipped to a 1!
5 (101) has exactly one more 1 than 4 (100).
If i is Odd: dp[i] = dp[i - 1] + 1

function countBitsEvenOdd(n: number): number[] {
    const dp = new Array(n + 1).fill(0);

    for (let i = 1; i <= n; i++) {
        if (i % 2 === 0) {
            // Even! It's identical to its half.
            dp[i] = dp[i / 2]; 
        } else {
            // Odd! It's the previous Even number + 1.
            dp[i] = dp[i - 1] + 1;
        }
    }

    return dp;
}

Interview Questions

Q: Between dp[i >> 1] + (i & 1) and the Even/Odd modulo logic, which is better in an interview?
A: The bitwise shift dp[i >> 1] + (i & 1) is vastly superior. Modulo division (i % 2) and standard division (i / 2) are significantly slower mathematical operations at the CPU level compared to raw bit shifts. Writing the Bitwise DP solution proves you understand both Dynamic Programming and hardware-level optimization simultaneously.