Solution: Counting Bits

Statement#

Solution#

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

The naive approach for this solution would be to iterate through the string character by character. During the traversal, we convert each number to its binary representation, count the number of $1$ bits in each binary representation, and store the result in an array.

This approach would have a time complexity of $O(n \log n)$ and a space complexity of $O(n)$.

Optimized approach using dynamic programming#

The problem involves using a dynamic programming approach to calculate and store the count of $1$ bits and use it for future iterations. Let’s take an example to see how the previous count of $1$ bits helps to find the count of $1$ bits in future iterations.

For every digit, we know it can be an even number or an odd number. Let’s see how we can compute each by using binary manipulation:

1. For even numbers, the count can be calculated using the count for half of that number. For example, the count of $1$ bit for $6$ equals the count of $1$ bit for $3$. We can confirm this by looking at the binary representation of $6$ and $3$, which are $0110$ and $0011$, respectively. The count of $1$ bit is two in both numbers.

2. For odd numbers, the count is one more than the count for half of that number. For example, the count of $1$ bit for $7$ equals the count of $1$ bit for $(7/2) = 3 + 1$ extra bit. We can confirm this by looking at the binary representation $7$ of and $3$, which are $0111$ and $0011 + 1$, respectively. The final count of $1$ bit after adding an extra $1$ bit to the half number is three.

Now, let’s look at the basic algorithm to solve this problem:

1. Add base cases where the $0^{th}$ and $1^{st}$ iteration results will be $0$ and $1$.

2. Create a 1D table of length $n+1$ containing all zeros. This will be used to store and recalculate the count of the $1$ bits in future iterations.

3. Next, we’ll iterate through the range of numbers from $2$ to $n$. If the number is even for each number in the range, compute result[x] = result[x // 2]. If the number is odd, compute result[x] = result[x // 2] + 1.

4. Finally, return the list containing the number of set bits in the binary representation of the numbers from $0$ to $n$.

The following illustration shows these steps in detail:

Let’s look at the code for this solution below:

Solution summary#

The solution above can be summarized in the following points:

• A DP array is created to store the result of any subproblems encountered during iteration.

• During the iteration, we performed two checks for even and odd numbers:

  • If the current number is even, then search and replace the current index’s value of the DP array with the value stored at half of this number. This is because both digits will have the same number of $1$ bits.

  • Otherwise, add an additional $1$ bit in the case of odd numbers.

• Return the last index of the DP array containing the number of set bits in the binary representation of the numbers from $0$ to $n$.

Time complexity#

The time complexity of this solution is $O(n)$ because the number of operations required for each integer $x$ within the range of $1$ to $n$ is constant and is not affected by the number of bits in $x$.

Space complexity#

The space complexity of this solution is $O(n)$.