# Counting Bits
**Difficulty:** EASY
[External](https://leetcode.com/problems/counting-bits)
Canonical: https://scaleengineer.com/dsa/problems/counting-bits
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Companies:** [Nvidia](https://scaleengineer.com/companies/nvidia)
---
## 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`.

**Example 1:**

**Input:** n = 2
**Output:** [0,1,1]
**Explanation:**
0 --> 0
1 --> 1
2 --> 10

**Example 2:**

**Input:** n = 5
**Output:** [0,1,1,2,1,2]
**Explanation:**
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

**Constraints:**

* `0 <= n <= 105`

**Follow up:**

* It is very easy to come up with a solution with a runtime of `O(n log n)`. Can you do it in linear time `O(n)` and possibly in a single pass?
* Can you do it without using any built-in function (i.e., like `__builtin_popcount` in C++)?

# Approaches
## Brute Force: Iterate and Count Bits
This is a straightforward brute-force approach. We iterate through each number from 0 to `n`. For each number, we manually count the number of set bits (1s) in its binary representation by repeatedly checking the last bit and shifting.
**Time:** O(n log n) - The outer loop runs `n + 1` times. For each number `i`, the inner while loop runs `log(i)` times (the number of bits in `i`). Therefore, the total time complexity is the sum of `log(i)` for `i` from 1 to `n`. · **Space:** O(n) - The space required is for the output array `ans` of size `n + 1`. If the output array is not considered, the space complexity is O(1).
**Pros:** Simple to understand and implement.; Does not require any complex mathematical insights.
**Cons:** Inefficient compared to linear time solutions.; It recomputes the bit count for each number from scratch, ignoring relationships between numbers.
### Explanation
The algorithm iterates through each integer from `0` to `n`. For each integer `i`, it calculates the number of set bits. This is done using a nested loop where we check the least significant bit (LSB) of the current number. If the LSB is `1`, we increment a counter. Then, we perform a right bit shift on the number to discard the LSB and check the next bit. This process is repeated until the number becomes `0`. The final count for `i` is stored in `ans[i]`.

```java
public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int count = 0;
        int num = i;
        while (num > 0) {
            count += num & 1;
            num >>= 1;
        }
        ans[i] = count;
    }
    return ans;
}
```
### Algorithm
- Initialize an array `ans` of size `n + 1`.
- Loop `i` from `0` to `n`:
  - Initialize `count = 0` and `num = i`.
  - While `num > 0`:
    - Add the last bit to the count: `count += num & 1`.
    - Right shift the number to process the next bit: `num >>= 1`.
  - Store the result: `ans[i] = count`.
- Return `ans`.

## Dynamic Programming with Least Significant Bit (LSB)
This approach uses dynamic programming to achieve a linear time solution. It finds a recurrence relation between the bit count of a number `i` and the bit count of a smaller, related number. By observing the relationship between `i` and `i / 2` (or `i >> 1`), we can compute the result in a single pass.
**Time:** O(n) - We iterate from `1` to `n` in a single pass, and each step involves constant time bitwise operations. · **Space:** O(n) - To store the result array `ans` of size `n + 1`.
**Pros:** Highly efficient with O(n) time complexity.; Solves the problem in a single pass, satisfying the follow-up.; The solution is elegant and concise.
**Cons:** Requires O(n) space for the DP table, although this is used for the output array.
### Explanation
The core idea is that the number of set bits in `i` is closely related to the number of set bits in `i >> 1` (i.e., `i` shifted right by one bit).

- If `i` is an even number, its binary representation is the same as `i/2` with a `0` appended. Thus, they have the same number of set bits. `countBits(i) = countBits(i/2)`.
- If `i` is an odd number, its binary representation is the same as `i/2` with a `1` appended. Thus, it has one more set bit than `i/2`. `countBits(i) = countBits(i/2) + 1`.

These two cases can be combined into a single, elegant formula: `countBits(i) = countBits(i >> 1) + (i & 1)`. The term `(i & 1)` evaluates to `0` for even `i` and `1` for odd `i`. We can build our `ans` array iteratively using this recurrence, as `ans[i >> 1]` will always have been computed before we calculate `ans[i]`.

```java
public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        // ans[i >> 1] is the bit count of i without its last bit.
        // (i & 1) is the value of the last bit of i.
        ans[i] = ans[i >> 1] + (i & 1);
    }
    return ans;
}
```
### Algorithm
- Initialize an array `ans` of size `n + 1`.
- The base case `ans[0]` is `0`.
- Loop `i` from `1` to `n`:
  - Apply the recurrence relation: `ans[i] = ans[i >> 1] + (i & 1)`.
- Return `ans`.

## Dynamic Programming with Brian Kernighan's Algorithm
This is another highly efficient dynamic programming approach that leverages a clever bit manipulation trick. The core idea is that for any number `x`, the expression `x & (x - 1)` clears the rightmost set bit. This property allows us to establish a different recurrence relation.
**Time:** O(n) - A single loop from `1` to `n` with constant time operations inside. · **Space:** O(n) - The space is dominated by the output array of size `n + 1`.
**Pros:** Achieves optimal O(n) time complexity in a single pass.; Demonstrates a powerful and widely applicable bit manipulation technique.; Very concise and efficient implementation.
**Cons:** The logic behind `i & (i - 1)` might be slightly less intuitive for beginners compared to the LSB approach.
### Explanation
The trick, sometimes associated with Brian Kernighan's algorithm, is that `i & (i - 1)` results in a number that is identical to `i` but with its rightmost '1' bit flipped to '0'. This means `i & (i - 1)` has exactly one fewer set bit than `i`.

This observation gives us the recurrence relation: `countBits(i) = countBits(i & (i - 1)) + 1`.

Since `i & (i - 1)` is always smaller than `i`, we can guarantee that `ans[i & (i - 1)]` has already been computed when we need to calculate `ans[i]`. We can build our solution array iteratively from `1` to `n` using this principle.

```java
public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        // i & (i - 1) has one less set bit than i.
        ans[i] = ans[i & (i - 1)] + 1;
    }
    return ans;
}
```
### Algorithm
- Initialize an array `ans` of size `n + 1`.
- The base case `ans[0]` is `0`.
- Loop `i` from `1` to `n`:
  - Apply the recurrence relation: `ans[i] = ans[i & (i - 1)] + 1`.
- Return `ans`.

# Solutions
### Java

```java
class Solution {
public
  int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 1; i <= n; ++i) {
      ans[i] = ans[i & (i - 1)] + 1;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> countBits(int n) {
    vector<int> ans(n + 1);
    for (int i = 0; i <= n; ++i) {
      ans[i] = __builtin_popcount(i);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countBits(self, n: int) -> List[int]: ans = [0] * (n + 1) for i in range(1, n + 1): ans[i] = ans[i & (i - 1)] + 1 return ans

```