Leetcode 338. Counting Bits
Problem Explanation
This problem is asking us to find the number of 1's in the binary representation for every number from 0 up to a given integer number and return them as an array.
For instance, given an input of 2, the numbers we have to check are 0, 1, 2. In binary, 0 is 0, 1 is 1, and 2 is 10. So, the number of 1's in their binary representation is [0], [1], and [1] respectively. Thus, the output would be [0, 1, 1].
Approach
The approach in this solution is using a variation of the dynamic programming with the property of bitwise operation which in this case i AND 1 equals to i % 2
, and i divided by 2
is the same as i shifted to the right by one bit
.
We will compute the number of 1's in a binary number from 0 to n
and store the result in a list.
For each number i
, the number of 1's in its binary representation is the sum of the number of 1's in the binary representation of i / 2
(which is basically removing the last digit) and the last digit i % 2
.
Example
To illustrate, let's take the input 5. The numbers we have to check are 0, 1, 2, 3, 4, and 5. In binary, these numbers are [0], [1], [10], [11], [100], and [101]. The number of 1's in their binary representations would be [0], [1], [1],[2],[1],[2] respectively and thus, the output would be [0,1,1,2,1,2].
Now, the algorithm would work as follows:
i=0 : ans[0] = ans[0/2] + 0%2 = ans[0] + 0 = 0
i=1 : ans[1] = ans[1/2] + 1%2 = ans[0] + 1 = 1
i=2 : ans[2] = ans[2/2] + 2%2 = ans[1] + 0 = 1
i=3 : ans[3] = ans[3/2] + 3%2 = ans[1] + 1 = 2
i=4 : ans[4] = ans[4/2] + 4%2 = ans[2] + 0 = 1
i=5 : ans[5] = ans[5/2] + 5%2 = ans[2] + 1 = 2
And finally, the resulting output array would be: [0, 1, 1, 2, 1, 2] thus the algorithm is proven to work.
Solutions
Python Solution
1 2python 3class Solution(object): 4 def countBits(self, num): 5 """ 6 :type num: int 7 :rtype: List[int] 8 """ 9 ans = [0] * (num + 1) 10 11 for i in range(1, num + 1): 12 ans[i] = ans[i >> 1] + (i & 1) 13 14 return ans
Java Solution
1 2java 3class Solution { 4 public int[] countBits(int num) { 5 int[] ans = new int[num + 1]; 6 7 for (int i = 1; i <= num; ++i) { 8 ans[i] = ans[i >> 1] + (i & 1); 9 } 10 11 return ans; 12 } 13}
JavaScript Solution
1 2javascript 3var countBits = function(num) { 4 let ans = Array(num + 1).fill(0); 5 6 for (let i = 1; i <= num; ++i) { 7 ans[i] = ans[i >> 1] + (i & 1); 8 } 9 10 return ans; 11};
C++ Solution
1
2cpp
3class Solution {
4public:
5 vector<int> countBits(int num) {
6 vector<int> ans(num + 1);
7 for(int i = 1; i <= num; ++i){
8 ans[i] = ans[i>>1] + (i&1);
9 }
10 return ans;
11 }
12};
C# Solution
1 2csharp 3public class Solution { 4 public int[] CountBits(int num) { 5 int[] ans = new int[num + 1]; 6 for (int i = 1; i <= num; ++i) { 7 ans[i] = ans[i >> 1] + (i & 1); 8 } 9 return ans; 10 } 11}
In the above solutions, we use a dynamic programming approach to store the number of 1's in the binary representation of each number from 0 to num
. For each number i
, the number of 1's in their binary representation is the sum of the number of 1's in i / 2
and i % 2
.This approach has a time and space complexity of O(N), where N is the input num. More efficient solutions are possible with a deeper understanding of binary number characteristics, but this one provides an excellent trade-off between performance and ease of understanding.
Testing the Solutions
After implementing your solutions, you can further test them to ensure their correctness. Below are example tests for the Python version:
1 2python 3s = Solution() 4assert s.countBits(2) == [0, 1, 1] 5assert s.countBits(5) == [0, 1, 1, 2, 1, 2]
In Java:
1
2java
3Solution s = new Solution();
4assert Array.equals(s.countBits(2), new int[]{0, 1, 1});
5assert Array.equals(s.countBits(5), new int[]{0, 1, 1, 2, 1, 2});
In JavaScript:
1
2javascript
3var s = new Solution();
4console.assert(JSON.stringify(s.countBits(2)) === JSON.stringify([0, 1, 1]));
5console.assert(JSON.stringify(s.countBits(5)) === JSON.stringify([0, 1, 1, 2, 1, 2]));
Remember that the running time for these solutions is linear in the size of the input, so they should be appropriate for a wide range of problem instances. Happy coding!
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.