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

# 338. Counting Bits

```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/2]+i%2;
        }
        return ans;
    }
}
```