# LeetCode 338: Counting Bits

### Problem Overview

Given an integer `n`, return an array `ans` of length `n + 1` where `ans[i]` is the number of set bits in the binary representation of `i`.

* **Example:** `n = 5` → Output: `[0, 1, 1, 2, 1, 2]`
    
* **Constraints:** `0 <= n <= 10^5`
    

### Solution 1: Brute Force

This is the most intuitive approach. We iterate through each number from 0 to `n`, and for each number, we manually count its set bits.

**The Algorithm for counting bits of a single number** `i`**:**

1. Initialize a counter for the current number, e.g., `count = 0`.
    
2. Use a temporary variable `temp_num = i` to avoid modifying the main loop’s counter.
    
3. Use a `while` loop that continues as long as `temp_num` is not 0.
    
4. Check the LSB: Use the bitwise AND operator(&) to check if the least significant bit is a 1.
    
5. Shift to the Next Bit: Use the right shift operator (`>>`) to discard the LSB.
    
6. The loop terminates when the number becomes 0.
    

C++ implementation:

```cpp
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1);
        for (int i = 0; i <= n; ++i) {
            // Logic to count bits for each number 'i'
            int count = 0;
            int temp_num = i;
            while (temp_num != 0) {
                if ((temp_num & 1) == 1) { // or simply: if (temp_num & 1)
                    count++;
                }
                temp_num = temp_num >> 1;
            }
            ans[i] = count;
        }
        return ans;
    }
};
```

Complexity Analysis:

* Time Complexity: O(n \* log(n))
    
    * The outer `for` loop runs n + 1 times.
        
    * The inner `while` loop runs for a number of times equal to the number of bits in `i`, which is approximately log(i).
        
* Space Complexity: O(n)
    
    * We need O(n) space for the `ans` array that we return.