Leetcode: 338. Counting Bits

• Pattern: Compute a sequence of values of a function
• Pattern: Bitwise problem

Given an integer \(n\), the task is to generate an array \(a\) of \(n+1\) elements where \(a[i]\) is equal to the number of 1 bits in \(i\). The simplest solution is to iterate over each index \(i\) and use Leetcode: 191. Number of 1 Bits to compute \(a[i]\). The time complexity of this solution is \(O(n \log n)\). We can do better. Note that \(a[i]\) is equal to one plus \(a[j]\) where \(j\) is \(i\) with the last significant digit turned of. For example, \(i=3 (0b011)\) then \(j=2 (0b010)\) and \(i=12 (0b01100)\) then \(j=8 (0b01000)\). Luckily, it is easy to compute \(j\): \(i & (i - 1)\). With this observation, we can solve the problem in time complexity $O(n).

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

• Interview preparation: V