> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/bit-manipulation #concepts/programming/algorithms/dynamic-programming]
> [project group:: Neetcode 150]
> [difficulty:: easy]
> [status:: done]
> [link:: https://leetcode.com/problems/counting-bits/]
> [up:: [[Leetcode MOC]]]
## 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++)?
## Solution
### Mine
#### Python
```python
class Solution:
def countBits(self, n: int) -> List[int]:
ans = [0] * (n + 1)
for i in range(n + 1):
ones = 0
z = i
while z:
ones += z % 2
z = z >> 1
ans[i] = ones
return ans
```
DP solution
```python
class Solution:
def countBits(self, n: int) -> List[int]:
ans = [0] * (n + 1)
results_cache = {}
current_power = 1
for i in range(n + 1):
if current_power * 2 == i:
current_power = i
if results_cache.get(i - current_power) is not None:
ans[i] = results_cache[i] = results_cache.get(i - current_power) + 1
else:
results_cache[i] = ans[i] # 0
return ans
```
#### Rust
### Neetcode's
```python
class Solution:
def countBits(self, n: int) -> List[int]:
dp = [0] * (n + 1)
offset = 1
for i in range(1, n + 1):
if offset * 2 == i:
offset = i
dp[i] = 1 + dp[i - offset]
return dp
```
## Things I Learned
- Bit shifting 1 to the right is the equivalent of dividing the number by 2, while bit shifting 1 to the left is equivalent to multiplying the number by 2. [Source](https://www.educative.io/answers/what-are-bit-shift-operations)
- One way to count the number of ones in the binary representation of a number is to get mod 2 of the number (this will be 1 if it's odd, ie has a 1 in the ones place), then bit shift to the right by one, which moves the ten digit to the one digit (in binary representation, in decimal it divides by 2), and repeat.
## Scratchpad
For my solution I'll pre-create a list of size $n + 1$, then iterate over the length of that list, and for each position use the answer from [[191. Number of 1 Bits]] to compute the number of ones at each position (while z isn't 0, add to `ones` the value of z mod 2 to know if there is a 1 at the ones position, then shift the bits 1 to the right (equivalent of dividing b 2). This is the $O(n\:log\:n)$ solution, though, because you iterate over the size of the list ($n$ times) and for each number you divide by 2 over and over, which is $log\:n$,
### Neetcode Notes
BUT, think about repeated work:
![[Pasted image 20230131212914.png]]
When we get to 4, we will have one extra 1 in the most significant bit. So the number of ones in 4 is just $1 + dp[0]$: 1 plus the number of ones in 0. We can generalize this to $1 + dp[n - 4]$
**BUT** this only holds for 4-7. When you get to 8, you need to go all the way back to 0, for $1 + dp[n - 8]$
The number you substract from $n$ is known as the **offset**. This is the most significant bit you've reached. e.g. 1, 2, 4, 8, 16, ....
For more generalization:
- 1 -> 0001 -> $1 + dp[n - 1]$ (1 is most significant bit)
- 2 -> 0010 -> $1 + dp[n - 2]$ (2 is most significant bit)
- 3 -> 0011 -> $1 + dp[n-2]$ (2 is still most significant bit)
How to know if you're at a new power of 2? previous power of 2 * 2 == new num