Leetcode – Counting Bits Solution in Python

Spread the love

In this comprehensive article, we will delve deep into a popular problem on LeetCode known as the ‘Counting Bits’. This problem is important in understanding bit manipulation techniques and dynamic programming. We will go through the problem statement, explore different approaches to solve the problem, and analyze their respective time and space complexities.

Introduction

First, let’s examine the problem statement:

Given a non-negative integer n, write a function to return an array ans where ans[i] is the number of 1‘s in the binary representation of i for 0 <= i <= n.

Example:

Input: n = 5

Output: [0,1,1,2,1,2]

Explanation:

0 –> 0 –> 0 1’s

1 –> 1 –> 1 1’s

2 –> 10 –> 1 1’s

3 –> 11 –> 2 1’s

4 –> 100 –> 1 1’s

5 –> 101 –> 2 1’s

Understanding the Problem

The problem asks us to calculate the number of 1‘s in the binary representation for all numbers from 0 to n. This problem can be solved through various approaches, including brute force and optimized methods.

Approach 1: Brute Force

One simple approach is to convert each number from 0 to n to its binary representation and count the number of 1‘s.

  1. Initialize an empty array result.
  2. Iterate through numbers i from 0 to n: a. Convert i to binary and count the number of 1‘s. b. Append the count to result.
  3. Return result.
def countBits(n):
    def countOnes(x):
        # Count the number of ones in binary representation of x
        return bin(x).count('1')
    
    result = [countOnes(i) for i in range(n + 1)]
    return result

Time Complexity:

O(nk) – where n is the given number and k is the average number of bits in the binary representation.

Space Complexity:

O(n) – Storing the result array.

Approach 2: Dynamic Programming (Bit Manipulation)

We can optimize the brute force approach by using bit manipulation and dynamic programming. We notice that for a number x, the number of bits in x is 1 plus the number of bits in x without its least significant bit. In other words, bits[x] = bits[x >> 1] + (x & 1).

  1. Initialize an array bits of size n+1 with all zeros.
  2. Iterate through numbers i from 1 to n: a. Set bits[i] = bits[i >> 1] + (i & 1).
  3. Return bits.
def countBits(n):
    bits = [0] * (n + 1)
    
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)
        
    return bits

Time Complexity:

O(n) – We iterate through all numbers from 1 to n once.

Space Complexity:

O(n) – Storing the result array.

Approach 3: Dynamic Programming (Smallest Power of Two)

We can further optimize the approach by observing that for any number x, the number of 1‘s in its binary representation can be obtained by 1 plus the number of 1‘s in x minus the smallest power of two greater than x. Specifically, bits[x] = bits[x - 2^m] + 1 where 2^m is the smallest power of two greater than x.

  1. Initialize an array bits of size n+1 with all zeros.
  2. Set offset = 1.
  3. Iterate through numbers i from 1 to n: a. If i is a power of two, set offset to i. b. Set bits[i] = bits[i - offset] + 1.
  4. Return bits.
def countBits(n):
    bits = [0] * (n + 1)
    offset = 1
    
    for i in range(1, n + 1):
        if i == offset * 2:
            offset *= 2
        bits[i] = bits[i - offset] + 1
        
    return bits

Time Complexity:

O(n) – We iterate through all numbers from 1 to n once.

Space Complexity:

O(n) – Storing the result array.

Conclusion:

The Counting Bits problem on LeetCode is a prime example of how dynamic programming and bit manipulation can be used to optimize a brute force approach. This problem illustrates the importance of understanding the properties of binary representations and how it can lead to more efficient algorithms. The progression from the brute force approach to more optimized solutions teaches a systematic way of thinking for optimization and can be invaluable in coding interviews and real-world applications.

Leave a Reply