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!