Dynamic Programming
Counting Bits
easy
Count: 10
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?
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
Visualization
Python
Try these examples:
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
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.