Dynamic Programming
Counting Bits
easy
DESCRIPTION (inspired by Leetcode.com)
Write a function that, given an integer n, returns an array dp of size n + 1, where dp[i] stores the count of '1' bits in the binary form of i.
Input:
n = 6
Output:
[0,1,1,2,1,2,2]
Explanation:
0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101 6 --> 110
This problem is intended to give you practice with implementing a bottom-up dynamic programming solution.
To figure out the appropriate recurrence relationship, let's consider the binary representation of a number.
For example, we can split the number 9 in binary into two parts: the least significant bit (rightmost bit) and the rest of the bits. The rest of the bits are highlighted in green below, and is equal to 9 // 2 = 4 in binary.
For the number 8, the rest of the bits is also equal to 8 // 2 = 4 in binary.
In general, the "rest of bits" of any number i is equal to i // 2. Try to use that information to figure out the recurrence relationship.
In other words, assume you know the number of 1's in the binary representation of i // 2. How can you use that information to calculate the number of 1's in the binary representation of i?
Code Editor
Python
Run your code to see results here
Have suggestions or found something wrong?
Explanation
This solution uses a bottom-up dynamic programming approach to solve the problem.
The key to this problem lies in the fact that any binary number can be broken down into two parts: the least-significant (rightmost bit), and the rest of the bits. The rest of the bits can be expressed as the binary number divided by 2 (rounded down), or i >> 1.
For example:
- 4 in binary = 100
- rightmost bit = 0
- rest of bits = 10, which is also (4 // 2) = 2 in binary.
When the number is odd,
- 5 in binary = 101
- rightmost bit = 1
- rest of bits = 10, which is also (5 // 2) = 2 in binary.
If we know the number of 1's in the binary representation of i // 2, then the number of 1's in the binary representation of i is that number plus 1 if the rightmost bit is 1. We can tell if the last significant bit is 1 by checking if it is odd.
As an example, we know that the number of 1's in 2 is 1. This information can be used to calculate the number of 1's in 4. The number of 1's in 4 is the number of 1's in 2 plus 0, because 4 is even.
This establishes a recurrence relationship between the number of 1's in the binary representation of i and the number of 1's in the binary representation of i // 2: if count[i] is the number of 1's in the binary representation of i, then count[i] = count[i // 2] + (i % 2).
With the recurrence relationship established, we can now solve the problem using a bottom-up dynamic programming approach. We start with the base case dp[0] = 0, and then build up the solution for dp[i] for i from 1 to n.
Visualization
Python
def count_bits(n):dp = [0] * (n + 1)for i in range(1, n + 1):dp[i] = dp[i // 2] + (i % 2)return dp
i = 1
0 / 5
Solution
Try these examples:
Visualization
Python
def count_bits(n):dp = [0] * (n + 1)for i in range(1, n + 1):dp[i] = dp[i // 2] + (i % 2)return dp
counting bits
0 / 12
Mark as read