LeetCode Solution 338 - 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 bits in the binary representation of i.

Example 1:

Input:

n = 2

Output:

[0,1,1]

Explanation:

• 0 -> 0 (0 bits)
• 1 -> 1 (1 bit)
• 2 -> 10 (1 bit)

Example 2:

Input:

n = 5

Output:

[0,1,1,2,1,2]

Explanation:

• 0 -> 0 (0 bits)
• 1 -> 1 (1 bit)
• 2 -> 10 (1 bit)
• 3 -> 11 (2 bits)
• 4 -> 100 (1 bit)
• 5 -> 101 (2 bits)

---

Optimal Approach: Dynamic Programming (DP) + Least Significant Bit

Why DP?

• We can use previously computed results to determine the number of 1 bits for each number efficiently.
• Using dp[i] = dp[i >> 1] + (i & 1), we avoid redundant calculations.

Algorithm:

1. Initialize an array dp of size n+1 with 0.
2. Iterate from 1 to n:
   • dp[i] = dp[i >> 1] + (i & 1).
3. Return dp as the result.

---

C++ Code Implementation

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
};

---

Step-by-Step Explanation

1. Initialize dp array with size n+1, all values set to 0.
2. Loop through 1 to n:
   • Compute dp[i] = dp[i >> 1] + (i & 1).
   • This means the count of 1s in i is the same as i/2, plus 1 if i is odd.
3. Return dp as the final result.

---

Dry Run

Input:

n = 5

Execution:

i	Binary	dp[i >> 1]	i & 1	dp[i]
0	0000	0	0	0
1	0001	0	1	1
2	0010	1	0	1
3	0011	1	1	2
4	0100	1	0	1
5	0101	1	1	2

---

Alternative Approaches

Approach	Time Complexity	Space Complexity	Reason for Rejection
Brute Force (Counting bits for each number)	O(n log n)	O(n)	Inefficient for large n
Bit Manipulation (n & (n - 1))	O(n log n)	O(n)	More complex than DP approach
Dynamic Programming (Best)	O(n)	O(n)	Most efficient and simple

---

Complexity Analysis

• Time Complexity: O(n), iterating through n once.
• Space Complexity: O(n), storing results in dp.

---

Conclusion

• Best Approach: Dynamic Programming with Least Significant Bit.
• Further Practice:
  • Number of 1 Bits
  • Power of Two
  • Reverse Bits

This solution efficiently computes the count of 1 bits for numbers up to n using Dynamic Programming, making it optimal for large inputs.