> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0338-counting-bits.md).

# 0338. Counting Bits

<https://leetcode.com/problems/counting-bits>

## Description

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++)?

## ac

```java
class Solution {
    public int[] countBits(int num) {
        // edge cases
        if (num < 0) throw new IllegalArgumentException("invalid input");

        // dp
        int[] dp = new int[num+1];
        dp[0] = 0;
        int base = 1;

        for (int i = 1; i <= num; i++) {
            if (i / base == 2) {
                dp[i] = 1;
                base = base << 1;
            } else {
                int idx = i % base;
                dp[i] = dp[idx] + 1;
            }
        }

        return dp;
    }
}
/*
power
f[i]
state: f[i] bit counts at i point
func: 1) if i/pow(2, power) == 2, f[i] = 1, power++;
        2) idx = i % pow(2, power), f[i] = f[idx] + 1;
init: f[0] = 0, power = 0
ans: f
*/
```

## ac2: bit manipulation

```java
class Solution {
    public int[] countBits(int num) {
        // edge case
        if (num < 0) return new int[0];

        int[] dp = new int[num+1];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = dp[i>>1] + (i&1);
        }

        return dp;
    }
}
```

## ac3: bit manipulation

```java
class Solution {
    public int[] countBits(int num) {
        // edge case
        if (num < 0) return new int[0];

        int[] dp = new int[num+1];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = dp[i&(i-1)] + 1;
        }

        return dp;
    }
}
```