[LeetCode] 338. Counting Bits

1. Question

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

2. Thoughts

get binary representation of each digit, and count '1'

3. Tips learned

3.1. Binary Representation

Use bin(i)

>>> bin(10)
'0b1010'
>>> 0b1010
10

3.2. Count occurance in string

The count() method returns the number of occurrences of a substring in the given string.

message = 'python is popular programming language'

# number of occurrence of 'p'
print('Number of occurrence of p:', message.count('p'))

# Output: Number of occurrence of p: 4

4. My solution

class Solution:
    def countBits(self, n: int) -> List[int]:
        return [bin(i)[2:].count("1") for i in range(n + 1)]

15/15 cases passed (71 ms)
Your runtime beats 65.1 % of python3 submissions
Your memory usage beats 48.01 % of python3 submissions (23.7 MB)

5. AI Solution and Improvements

Your solution for counting the number of 1's in the binary representation of each number up to n is correct. It uses Python's built-in bin() function to convert each number to its binary representation, then counts the number of 1's using the count() method of strings. This approach is simple and easy to understand but can be optimized in terms of time complexity.

An efficient way to solve this problem is to use dynamic programming. The idea is to recognize that the number of 1's in the binary representation of a number is related to its previous numbers. This relationship can be exploited using the concept that for any number i, the number of 1's in i is equal to 1 + the number of 1's in (i - the most significant bit of i). The most significant bit of i can be obtained by repeatedly right-shifting i until only the most significant bit remains.

Here's an optimized version of your solution using dynamic programming:

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i & (i - 1)] + 1
        return ans

Explanation:

• Create an array ans of size n + 1 to store the result. Initialize all elements to 0.
• Iterate from 1 to n, and for each number i, use the formula ans[i] = ans[i & (i - 1)] + 1. Here, i & (i - 1) clears the least significant bit of i, effectively giving us the result of i without its most significant bit.

1. Binary Representation and Most Significant Bit (MSB):

   • Every binary number can be considered as a sequence of 0's and 1's. For example, the binary representation of 5 is 101.
   • In a binary number, the most significant bit (MSB) is the bit that has the highest value. For instance, in the number 101 (5 in binary), the MSB is the leftmost 1.

2. Bitwise AND Operation (&):

   • The bitwise AND operation & takes two binary numbers and performs the logical AND operation on each pair of corresponding bits. The result is 1 if both bits are 1, and 0 otherwise.
   • An interesting property is when you perform i & (i - 1). This operation turns off (sets to 0) the least significant 1 bit in i.
     • For example, if i = 5 (which is 101 in binary), then i - 1 = 4 (100 in binary). So, i & (i - 1) equals 101 & 100, which results in 100 (or 4 in decimal).

3. The Expression ans[i] = ans[i & (i - 1)] + 1:

   • The idea is to use the already computed results (ans) for smaller numbers to compute the result for the current number (i).
   • i & (i - 1) gives us a number that is smaller than i and has one fewer 1 bit in its binary representation because it removes the least significant 1 bit from i.
   • Therefore, ans[i & (i - 1)] gives us the count of 1 bits for this smaller number.
   • Since we removed exactly one 1 bit to get i & (i - 1) from i, we add 1 to ans[i & (i - 1)] to get the count of 1 bits for i.

In summary, this expression efficiently computes the number of 1's in the binary representation of i by building upon the previously computed results, thus avoiding recalculating from scratch for each number. This dynamic programming technique significantly optimizes the process, especially for large values of n.

• Return the ans array.