Counting Bits | Leetcode 338

Welcome to our deep dive on Counting Bits (Leetcode 338). This problem brilliantly combines Bitwise operations and Dynamic Programming!

Problem Statement

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: n = 5 => Output: [0,1,1,2,1,2] (Explanation: 0 --> 0, 1 --> 1, 2 --> 10, 3 --> 11, 4 --> 100, 5 --> 101)

Approach 1: Bit Manipulation Iteration O(N log N)

The standard way to count the number of set bits (1s) in any integer is using an algorithm called Brian Kernighan's Algorithm. We can apply this algorithm iteratively for every single number from 0 to n.

n & (n - 1) essentially cleanly flips the rightmost 1 bit in n to a 0. We can simply count how many times we run this operation until the number hits 0.

class Solution:
    def countBits(self, n: int) -> List[int]:
        res = []
        
        for i in range(n + 1):
            count = 0
            num = i
            while num:
                num &= (num - 1)
                count += 1
            res.append(count)
            
        return res

Complexity Analysis

Approach 2: DP + Bit Manipulation Optimization O(N)

We can optimize this significantly! The number of 1s in the binary representation of integer i is deeply mathematically related to numbers smaller than i.

Notice the bit shift operation: When we divide a number by 2 (by doing a right bit-shift i >> 1), we completely drop the rightmost bit.

• Example: i = 6 (in binary 110). 6 >> 1 is 3 (011). The number of bits in 6 exactly neatly matches the number of bits in 3!
• Example: i = 7 (in binary 111). 7 >> 1 is 3 (011). The number of bits in 7 is the number of bits in 3, plus 1!

This mathematically explicitly strictly means: DP[i] = DP[i >> 1] + (i & 1)

• i >> 1 looks up the answer we already explicitly calculated recursively identically successfully for i / 2.
• i & 1 cleanly resolves to 1 mathematically seamlessly identically if the rightmost bit dynamically was a 1 (which means i is an odd number), or 0 if i is even!

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

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (338)