LeetCode: Counting Bits — Optimal Solution Explained

LeetCode: Counting Bits — Optimal Solution Explained

Table of Content

• Introduction
• Intuition/Solution
• Step-by-Step Visual Guide
• Implementation Code

Introduction

Counting bits can be done pretty easily with brute force simply by converting each integer to bits and then counting the 1’s. However, we’ll discuss the key intuition and optimal solution for this problem using dynamic programming.

We will guide you step by step, using clear visuals to demonstrate how the solution works with time complexity of O(n) and space complexity of O(n)

Intuition/Solution

The key intuition for this problem is to look at the pattern formed in the binary representation of each integer.

Number      Binary  Count of 1 bits
  0          0000          0
  1          0001          1
  
  2 (even)   0010          1
  3 (odd)    0011          2
  
  4 (even)   0100          1
  5 (odd)    0101          2
  
  6 (even)   0110          2
  7 (odd)    0111          3
  
  8 (even)   1000          1
  9 (odd)    1001          2
  
  10 (even)  1010          2
  11 (odd)   1011          3
  
  12 (even)  1100          2
  13 (odd)   1101          3
  
  14 (even)  1110          3
  15 (odd)   1111          4

Let’s take a look at some patterns in the number of 1 bits:

• For any even number x, the number of 1 bits is the same as the number of 1 bits in x/2. This is because dividing by 2 is equivalent to right-shifting the binary representation, and the least significant bit (which is 0 for even numbers) is removed.
• For any odd number y, the number of 1 bits is 1 more than the number of 1 bits in y-1. This is because when you subtract 1 from an odd number, the least significant bit (which is 1 for odd numbers) is removed.

After realizing this pattern, the key intuition for this problem is to use previously calculated results to find the number of 1 bits in the binary representation of the current number, to avoid redundant calculations.

Using the above intuition, we can create a dynamic programming solution to calculate the number of 1 bits for each number in the range [0, n]:

1. Create an array dp of size n+1 to store the number of 1 bits for each number.
2. Initialize dp[0] to 0, as there are no 1 bits in the binary representation of 0.
3. Loop through numbers from 1 to n (inclusive):
   - If the number is even, set dp[i] to dp[i/2]
   - If the number is odd, set dp[i] to dp[i-1] + 1
4. Return the dp array.

The time complexity of this solution is O(n), and the space complexity is also O(n) to store the dp array.

Step-by-Step Visual Guide

Example

Let’s go through the “Counting Bits” problem solution visually where n=6

n = 6
result = [0, 0, 0, 0, 0, 0, 0]

1. i = 1 (odd)
   result[1] = result[1 - 1] + 1 = result[0] + 1 = 0 + 1 = 1
   result = [0, 1, 0, 0, 0, 0, 0]

2. i = 2 (even)
   result[2] = result[2 / 2] = result[1] = 1
   result = [0, 1, 1, 0, 0, 0, 0]

3. i = 3 (odd)
   result[3] = result[3 - 1] + 1 = result[2] + 1 = 1 + 1 = 2
   result = [0, 1, 1, 2, 0, 0, 0]

4. i = 4 (even)
   result[4] = result[4 / 2] = result[2] = 1
   result = [0, 1, 1, 2, 1, 0, 0]

5. i = 5 (odd)
   result[5] = result[5 - 1] + 1 = result[4] + 1 = 1 + 1 = 2
   result = [0, 1, 1, 2, 1, 2, 0]

6. i = 6 (even)
   result[6] = result[6 / 2] = result[3] = 2
   result = [0, 1, 1, 2, 1, 2, 2]

At the end of the loop, we have the array result containing the count of 1 bits for each number from 0 to n (inclusive): [0, 1, 1, 2, 1, 2, 2].

Implementation Code

Python

def count_bits(num):
    result = [0] * (num + 1)

    for i in range(1, num + 1):
        if i % 2 == 0:
            result[i] = result[i // 2]
        else:
            result[i] = result[i - 1] + 1

    return result

Javascript

function countBits(num) {
    let result = new Array(num + 1).fill(0);

    for (let i = 1; i <= num; i++) {
        if (i % 2 === 0) {
            result[i] = result[i / 2];
        } else {
            result[i] = result[i - 1] + 1;
        }
    }

    return result;
}