LeetCode #338: Counting Bits

LeetCode Solutions

https://leetcode.com/problems/counting-bits/

We need to find the number of 1’s in the binary representation of each number from 0 to n. One way to do this is to use the bitwise AND operator with a mask that has only one bit set to 1 at each position, and count the number of times this operation returns a non-zero value.

An easier way to solve this problem is to use dynamic programming. We can observe that the number of 1’s in the binary representation of a number n is equal to the number of 1’s in the binary representation of n/2 plus the least significant bit of n. We can use this observation to compute the number of 1’s in the binary representation of each number from 0 to n.

We can start with the base case of ans[0] = 0, since the binary representation of 0 has no 1’s. Then, we can iterate through the numbers from 1 to n, and for each number i, compute ans[i] as ans[i // 2] + (i % 2).

  1. Create an array of size n+1 to hold the number of 1’s in the binary representation of each number from 0 to n.
  2. Initialize ans[0] = 0, since the binary representation of 0 has no 1’s.
  3. Iterate through the numbers from 1 to n, and for each number i, compute ans[i] as ans[i // 2] + (i % 2).
  4. Return the array ans.
class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0]*(n+1)
        for i in range(1, n+1):
            ans[i] = ans[i // 2] + (i % 2)
        return ans

Time Complexity

The time complexity of this solution is O(n), where n is the input integer. We need to iterate over every integer from 0 to n and perform constant time operations on each integer.

Space Complexity

The space complexity of this solution is also O(n), as we need to create an array to store the number of 1 bits for each integer from 0 to n.