[LeetCode] 338. Counting Bits

435. Counting Bits

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.

 

 

1. Problem Understanding

The problem asks us to count the number of 1s (set bits) in the binary representation of every integer from 0 to n. The result should be returned as an array where the value at index i represents the count of set bits in the binary representation of i.

 

2. Core Concepts

' Binary Representation:

- Binary is a base-2 number system where each digit represents a power of 2.

' Key Observations

- Any number i can be broken down as:

  - i >> 1: This is the number i divided by 2 (dropping the least significant bit)

  - i & 1 :  This checks whether the least significant bit (LSB) of i or 1 or 0.

' Dynamic Programming Insight

- Using the above formula, we can compute the number of set bits for i by reusing the results we computed for smaller numbers. This is an example of a bottom-up dynamic programming approach.

 

3. Key Bitwise Operations

' Right Shift (>>)

- Shifts the bits of a number to the right, effectively dividing the number by 2

' Bitwise And (&):

- Compares each bit of two number and returns 1 if both bits are 1

- Check if a number is odd or even

' Bitwise OR(|) and XOR(^)

- OR: Returns 1 if at least one bit is 1

- XOR: Returns 1 if the bits are different

 

 

 

 

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

        for i in range(1, len(ans)):
            ans[i] = ans[i >> 1] + (i & 1)

        return ans