Counting Bits

This blog series attempts to solve the 500 Top Leet Code Interview Questions with the help of AI Code Assistance, such as Gemini and GPT.

Question 168:

Counting Bits

We need to generate an array where each element at index i represents the count of 1s in the binary representation of i.

Constraints:

• The naive solution runs in O(n log n) because each number requires counting bits one by one.
• We aim for O(n) linear time complexity.
• We cannot use built-in functions like __builtin_popcount().

Optimal Solution

Key Observations:

Bitwise Relation:

• The number of 1s in i can be derived from a previously computed value.
• i >> 1 (i.e., i // 2) removes the least significant bit.
• If i is even: count(i) = count(i // 2), because the last bit is 0.
• If i is odd: count(i) = count(i // 2) + 1, because the last bit is 1.

Formula:

• ans[i] = ans[i >> 1] + (i & 1)

This approach allows us to calculate each value in O(1) time, leading to an O(n) overall complexity.

Code Implementation

def countBits(n):
    ans = [0] * (n + 1)
    
    for i in range(1, n + 1):
        ans[i] = ans[i >> 1] + (i & 1)…