Counting Bits

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.

Examples

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 → 0 (binary) → 0 ones
1 → 1 (binary) → 1 one
2 → 10 (binary) → 1 one

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 → 0 (binary) → 0 ones
1 → 1 (binary) → 1 one
2 → 10 (binary) → 1 one
3 → 11 (binary) → 2 ones
4 → 100 (binary) → 1 one
5 → 101 (binary) → 2 ones

Constraints

• 0 <= n <= 10^5

Solution Approaches

Approach 1: Brute Force - Count Bits for Each Number

Simply count 1-bits for each number individually.

public int[] countBits(int n) {
    int[] result = new int[n + 1];

    for (int i = 0; i <= n; i++) {
        result[i] = countOnes(i);
    }

    return result;
}

private int countOnes(int num) {
    int count = 0;
    while (num > 0) {
        count += num & 1;
        num >>= 1;
    }
    return count;
}

Time Complexity: O(n × log n) - For each number, we count bits Space Complexity: O(1) - Not counting output array

This works but is not optimal!

Approach 2: Dynamic Programming - Last Bit Pattern ⭐

Key Insight: We can use previously computed results!

Pattern Discovery:

i    Binary   Ones   i>>1  (i>>1) binary  Last bit (i&1)
0    0        0      -     -               -
1    1        1      0     0               1
2    10       1      1     1               0
3    11       2      1     1               1
4    100      1      2     10              0
5    101      2      2     10              1
6    110      2      3     11              0
7    111      3      3     11              1

Observation:

• i >> 1 removes the last bit (divides by 2)
• i & 1 gets the last bit (0 or 1)
• bits[i] = bits[i >> 1] + (i & 1)

Why this works?

• Removing last bit gives us a smaller number we've already computed
• We just need to add back the last bit!

Example: For i = 5 (binary: 101)

• 5 >> 1 = 2 (binary: 10)
• 5 & 1 = 1 (last bit)
• bits[5] = bits[2] + 1 = 1 + 1 = 2 ✓

Approach 3: DP - Last Set Bit Pattern

Alternative Pattern:

bits[i] = bits[i & (i-1)] + 1

What is i & (i-1)?

• It removes the rightmost set bit (rightmost 1)

Example: For i = 6 (binary: 110)

• i - 1 = 5 (binary: 101)
• i & (i-1) = 110 & 101 = 100 (4)
• bits[6] = bits[4] + 1 = 1 + 1 = 2 ✓

This is Brian Kernighan's algorithm applied to DP!

Approach 4: DP - Offset Pattern

Another Pattern:

bits[i] = bits[i - offset] + 1

where offset is the largest power of 2 ≤ i

Example:

For i = 5:
- Largest power of 2 ≤ 5 is 4
- bits[5] = bits[5-4] + 1 = bits[1] + 1 = 1 + 1 = 2

Time & Space Complexity

All DP Approaches:

• Time Complexity: O(n)

  • Single pass through 0 to n
  • Each computation is O(1)

• Space Complexity: O(1)

  • Not counting output array
  • Only using a few variables

Java Solution (Approach 2 - Recommended)

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            // bits[i] = bits[i/2] + (i % 2)
            bits[i] = bits[i >> 1] + (i & 1);
        }

        return bits;
    }
}

Python Solution

def countBits(n: int) -> List[int]:
    bits = [0] * (n + 1)

    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)

    return bits

Java Solution (Approach 3)

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i & (i - 1)] + 1;
        }

        return bits;
    }
}

Visual Pattern Analysis

Approach 2 Visualization (i >> 1):

i=0: 0     → parent: -      → bits[0] = 0
i=1: 1     → parent: 0 (0)  → bits[1] = bits[0] + 1 = 0+1 = 1
i=2: 10    → parent: 1 (1)  → bits[2] = bits[1] + 0 = 1+0 = 1
i=3: 11    → parent: 1 (1)  → bits[3] = bits[1] + 1 = 1+1 = 2
i=4: 100   → parent: 2 (10) → bits[4] = bits[2] + 0 = 1+0 = 1
i=5: 101   → parent: 2 (10) → bits[5] = bits[2] + 1 = 1+1 = 2
i=6: 110   → parent: 3 (11) → bits[6] = bits[3] + 0 = 2+0 = 2
i=7: 111   → parent: 3 (11) → bits[7] = bits[3] + 1 = 2+1 = 3

Approach 3 Visualization (i & (i-1)):

i=1: 1     → 1 & 0 = 0     → bits[1] = bits[0] + 1 = 1
i=2: 10    → 10 & 1 = 0    → bits[2] = bits[0] + 1 = 1
i=3: 11    → 11 & 10 = 10  → bits[3] = bits[2] + 1 = 2
i=4: 100   → 100 & 11 = 0  → bits[4] = bits[0] + 1 = 1
i=5: 101   → 101 & 100 = 100 → bits[5] = bits[4] + 1 = 2
i=6: 110   → 110 & 101 = 100 → bits[6] = bits[4] + 1 = 2
i=7: 111   → 111 & 110 = 110 → bits[7] = bits[6] + 1 = 3

Related Problems

• Number of 1 Bits (LeetCode 191): Count bits in single number
• Binary Watch (LeetCode 401): Uses bit counting
• Hamming Distance (LeetCode 461): XOR and count bits
• Total Hamming Distance (LeetCode 477): Bit counting across array
• Single Number (LeetCode 136): Bit manipulation

Pattern Recognition

This problem demonstrates:

• Dynamic Programming pattern
• Bit manipulation optimization
• Recurrence relation discovery
• Parent-child relationship in binary numbers

Common Mistakes

1. ❌ Using O(n log n) brute force when O(n) DP exists
2. ❌ Not recognizing the pattern between numbers
3. ❌ Confusing >> (right shift) with / (division) - they're the same for positives
4. ❌ Using % instead of & for last bit - & is faster
5. ❌ Not starting from index 0
6. ❌ Off-by-one errors (array size should be n+1)

Tips for Interviews

• Start with brute force: Mention O(n log n) solution first
• Pattern recognition: Draw the table showing i, binary, and ones
• Key insight: Explain the relationship between i and i>>1
• Bit operations: Clearly explain >> and &
• Multiple solutions: Mention at least 2 DP approaches
• Complexity: Emphasize O(n) time is optimal
• Follow-up: Be ready to explain alternative DP formulas

Follow-Up Questions

1. Q: Can you do better than O(n)?

   • A: No, we must fill n+1 array positions

2. Q: What if we only need bits[k] for specific k?

   • A: Still compute all up to k using DP (faster than counting bits of k alone if k is large)

3. Q: How does i & (i-1) remove the rightmost set bit?

   • A: i-1 flips all bits after rightmost 1, so AND zeros them

4. Q: Which DP approach is best?

   • A: Approach 2 (i>>1) is most intuitive and commonly used

Why Different DP Formulas Work

All three patterns work because:

1. They use previously computed smaller values
2. They add a constant (0 or 1) based on bit properties
3. They maintain optimal substructure

The relationship:

• Approach 2: Remove last bit, add it back
• Approach 3: Remove rightmost 1, add 1
• Approach 4: Subtract largest power of 2, add 1

All give the same result but have different thought processes!

Complexity Comparison

| Approach | Time | Space | Notes | |----------|------|-------|-------| | Brute Force | O(n log n) | O(1) | Count each number separately | | DP (i>>1) | O(n) | O(1) | Most intuitive ⭐ | | DP (i&(i-1)) | O(n) | O(1) | Brian Kernighan pattern | | DP (offset) | O(n) | O(1) | Power of 2 based |

Recommendation: Use Approach 2 (i>>1 + last bit) for clarity and efficiency.

Key Formulas

Main Formula (Approach 2):

bits[i] = bits[i >> 1] + (i & 1)

where:
- i >> 1 is i divided by 2 (parent)
- i & 1 is the last bit (0 or 1)

Alternative Formula (Approach 3):

bits[i] = bits[i & (i-1)] + 1

where:
- i & (i-1) removes the rightmost 1-bit

Bit Operation Cheat Sheet

• i >> 1 : Right shift = divide by 2 = remove last bit
• i & 1 : AND with 1 = get last bit (0 or 1)
• i & (i-1) : Remove rightmost 1-bit
• i & -i : Get rightmost 1-bit
• i | (i+1) : Set rightmost 0-bit

Understanding these operations is crucial for bit manipulation problems!