Problem of The Day: Counting Bits

Problem Statement

leetcode problem link

My Solution [Accepted]

class Solution:
    def countBits(self, n: int) -> List[int]:
        res = []
        for i in range(n + 1):
            count = 0
            x = i
            print('---')
            while x > 0:
                print(x, bin(x), bin(x - 1))
                x = x & (x - 1) # clear right most bit
                print(bin(x))
                count += 1
            res.append(count)

        return res

Editorial

Approach 1: Pop Count

class Solution:
    def countBits(self, n: int) -> List[int]:

        def pop_count(x: int) -> int:
            count = 0
            while x != 0:
                x &= x - 1 # zeroing out the least significant nonzero bit
                count += 1
            return count

        ans = [0] * (n + 1)
        for x in range(n + 1):
            ans[x] = pop_count(x)

        return ans

• Time: O(nlogn)

Approach 2: DP + Most Significant Bit

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        x = 0
        b = 1

        # [0, b) is calculated
        while b <= n:
            # generate [b, 2b) or [b, n) from [0, b)
            while x < b and x + b <= n:
                ans[x + b] = ans[x] + 1
                x += 1
            x = 0 # reset x
            b <<= 1 # b = 2b

        return ans

• Time: O(n)